균형 잡힌 줄 세우기

매일 젖을 짜기 위해 농부 존의 소 $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$개의 줄: 각 줄에는 해당 질의에 대한 답, 즉 주어진 구간에서 키가 가장 큰 소와 가장 작은 소의 키 차이를 나타내는 정수 하나를 출력합니다.