균형 잡힌 줄 세우기

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

존은 소들의 그룹 $Q$개($1 \le Q \le 200{,}000$)와 각 소의 키($1 \le \text{키} \le 1{,}000{,}000$)를 목록으로 만들었습니다. 각 그룹에 대해, 그 그룹에서 키가 가장 작은 소와 가장 큰 소의 키 차이를 구해 주세요.

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

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