균형 잡힌 줄 세우기

시간 제한1초메모리 제한128 MB

요약

소 N마리의 키와 Q개의 구간이 주어질 때, 각 구간에서 가장 큰 키와 가장 작은 키의 차이를 구한다.

난이도: 보통10점 중 6점
유형: 세그먼트 트리, 배열, 구현, 누적 합
정답자: 아직 제출이 없습니다

문제

매일 젖을 짜기 위해 농부 존의 소 $N$ 마리( $1 \le N \le 50000$ )는 항상 같은 순서로 줄을 섭니다. 어느 날 존은 소 몇 마리를 골라 얼티밋 프리스비 경기를 열기로 합니다. 간단하게 하기 위해, 줄에서 연속한 구간에 있는 소들만 경기에 참여시킵니다. 다만 모든 소가 즐겁게 경기하려면 키 차이가 너무 크지 않아야 합니다.

존은 소들의 키( $1 \le \text{키} \le 1000000$ )와 함께 $Q$ 개( $1 \le Q \le 180000$ )의 후보 구간을 준비했습니다. 각 구간에 대해, 그 구간에서 키가 가장 작은 소와 가장 큰 소의 키 차이를 구해 주세요.

참고: 가장 큰 테스트에서는 입출력이 실행 시간의 대부분을 차지합니다.

입력

첫째 줄: 공백으로 구분된 두 정수 $N$ 과 $Q$ .
둘째 줄부터 $N+1$ 번째 줄까지: $i+1$ 번째 줄에는 소 $i$ 의 키를 나타내는 정수 하나가 주어집니다.
$N+2$ 번째 줄부터 $N+Q+1$ 번째 줄까지: 두 정수 $A$ 와 $B$ ( $1 \le A \le B \le N$ )가 주어지며, 이는 $A$ 번째 소부터 $B$ 번째 소까지(양 끝 포함)의 구간을 의미합니다.

출력

$Q$ 개의 줄: 각 줄에는 해당 질의에 대한 답, 즉 주어진 구간에서 키가 가장 큰 소와 가장 작은 소의 키 차이를 나타내는 정수 하나를 출력합니다.

예제3

예제 1
입력
```
6 3
1
7
3
4
2
5
1 5
4 6
2 2
```
예상 출력
```
6
3
0
```
예제 2
입력
```
1 1
42
1 1
```
예상 출력
```
0
```
예제 3
입력
```
2 3
5
10
1 1
2 2
1 2
```
예상 출력
```
0
0
5
```