매일 젖을 짤 때 Farmer John의 $N$마리 소 ($1 \le N \le 50,000$)는 항상 같은 순서로 줄을 선다. 어느 날 Farmer John은 일부 소와 얼티밋 프리스비 경기를 하기로 한다. 간단히 하기 위해 젖 짜는 줄의 연속된 구간에 있는 소들을 골라 경기에 참여시킨다. 하지만 모든 소가 즐겁게 놀려면 키가 너무 많이 차이 나서는 안 된다.

Farmer John은 후보가 되는 $Q$개 ($1 \le Q \le 200,000$) 소 그룹과 소들의 키 ($1 \le height \le 1,000,000$)를 목록으로 만들었다. 각 그룹에 대해 가장 키가 큰 소와 가장 작은 소의 키 차이를 구하도록 도와라.

입력

표준 입력에서 입력을 읽는다.

1번째 줄: 공백으로 구분된 두 정수 $N$과 $Q$.

$2 \ldots N+1$번째 줄: $i+1$번째 줄에는 소 $i$의 키를 나타내는 정수 하나가 주어진다.

$N+2 \ldots N+Q+1$번째 줄: 두 정수 $A$와 $B$ ($1 \le A \le B \le N$). 양 끝을 포함하여 $A$부터 $B$까지의 소 구간을 나타낸다.

출력

표준 출력에 출력한다.

$1 \ldots Q$번째 줄: 각 줄에 해당 질의에 대한 답인 정수 하나를 출력한다. 이 정수는 구간에서 가장 키가 큰 소와 가장 작은 소의 키 차이이다.

예제

입력 1

6 3
1
7
3
4
2
5
1 5
4 6
2 2

출력 1

6
3
0

문제 출처: USACO 2007년 1월 Gold