문제
매일 우유를 만들고자 할 때, 농부 창호의 N(1≤N≤50,000)마리의 소는 항상 같은 순서로 줄을 서고 있다.
편의상 맨 앞에 선 소가 1번, 맨 마지막에 선 소가 N번으로 번호를 매겼다.
어느 날 농부 창호는 몇몇의 소들과 원반던지기 게임을 하고자 한다.
소들을 고르는 방법은 우유를 만들기 위해 줄을 서 있는 소들의 줄에서 임의적으로 한 연속된 구간을 선택해서 게임을 하고자 한다.
게임을 하기 전에 소들의 키가 너무 차이가 날 경우에는 게임이 너무 재미없어지기 때문에 창호는 게임을 하고자 하는 구간을 몇 개 고른 다음에,
해당 구간에 속한 소들의 가장 큰 키와 가장 작은 키의 차이가 얼마나 되는지 알아보고자 한다.
소들의 키가 주어지고, 창호가 알아보고자 하는 Q(1≤Q≤200,000)개의 구간이 주어졌을 때
각 구간에 대한 가장 큰 소와 가장 작은 소의 키 차이를 알아보는 프로그램을 작성하라.
입력
입력의 첫 번째 줄에는 N과 Q가 공백을 사이에 두고 입력된다.
그 다음 N개의 줄에는 순서대로 서있는 소들의 키 크기가 한 줄에 하나씩 입력되는데, 이는 1이상 1,000,000 이하이다.
소들의 키가 입력된 다음, Q개의 구간의 시작과 끝 A, B가 공백을 사이에 두고 입력되며,
A는 구간이 시작되는 소의 번호, B는 구간이 끝나는 소의 번호이며 A와 B는 1이상 N이하의 수이며 A는 B보다 작거나 같다.
출력
입력된 Q개의 구간에 대한 가장 큰 소의 크기와 가장 작은 소의 크기의 차이를 출력하는 프로그램을 작성한다.
예제1
입력
63
1
7
3
4
2
5
15
46
22
출력
6
3
0
힌트