1368 - 조 편성이 평등한가요?

Time Limit: 1s Memory Limit: 128MB

Submissions: 273 Solved: 49
Description

WithCS 농장의 아저씨는 N(1 ~ 50,000)명의 강아지를 관리하고 있습니다. 어느날 WithCS 농장 아저씨는 강아지의 건강을 위해 경쟁 프리스비 게임을 하기로 하였습니다.

조 구성을 쉽게 하기 위해 강아지 순서 번호룰 기준으로 연속적으로 묶어 하나의 조으로 만들었습니다. 모든 강아지가 즐겁게 즐기기 위해서는 하나의 조에 속한 강아지들의 키의 차이가 적어야 합니다. WithCS 농장의 아저씨는 Q(1 ~ 200,000)개의 조를 만들었습니다.

각각의 조에 대해 가장 큰 키를 가지는 강아지와, 가장 작은 키를 가지는 강아지의 키 차이를 알고 싶습니다.

Input

* Line 1 : 2개의 정수, N Q

    - N : 강아지의 수

    - Q : 조(group)의 수

* Line 2 ~ N+1 : 단일 정수 (강아지의 키)

* Line N+1 ~ N+Q+1 : 2개의 정수, A B

    - A : 조에 속한 강아지 시작 번호

    - B : 조에 속한 강아지 끝 번호

    - 예 : "1 5"인 경우 1번 강아지부터 5번 강아지까지 5마리가 한 조로 편성됨

Output

각각의 라인은 Q개의 조 각각에 대해 최소 키와 최대 키의 차이를 기록

Sample Input
6 3
1
7
3
4
2
5
1 5
4 6
2 2
Sample Output
6
3
0