Farmer John의 $N$마리($1 \le N \le 50,000$)는 매일 착유에 같은 순서로 섭니다. 어느 날 일부와 얼티밋 프리스비를 합니다. 간단히 연속 구간을 고르지만 모두 즐기려면 키 차이가 너무 크면 안 됩니다.

$Q$($1 \le Q \le 200,000$)후보 그룹과 키($1 \le height \le 1,000,000$) 목록에서 각 그룹 최장과 최단의 차이를 구하세요.

입력

표준 입력에서 읽으세요.

1번째 줄: 공백 구분 정수 $N$, $Q$.

$2..N+1$번째 줄: $i+1$번째 줄은 소 $i$의 정수 키.

$N+2$..$N+Q+1$번째 줄: 정수 $A$, $B$($1 \le A \le B \le N$), 양끝 포함 $A$부터 $B$.

출력

표준 출력에 쓰세요.

$1..Q$번째 줄: 각 정수 하나로 해당 질문 구간의 최대와 최소 키 차이.

예제

입력 1

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

출력 1

6
3
0

출처: USACO 2007년 1월 실버