매일 GT혹성의 닭들은 알을 낳기 위해 같은 순서로 줄을 선다.
하루는 종암심이 몇마리의 닭들과 닭싸움을 하기로 하였다.
게임을 위해서 현재 줄 선 그룹에서 일련의 몇 마리의 닭을 뽑기로 하였다.
이 게임에서는 뽑은 그룹에서 제일 큰 닭과 작은 닭의 키 차이를 알아야 한다.
종암심은 Q 개의 그룹과 그들의 키들의 리스트를 만들었다.
당신의 일은 각 그룹에서 가장 큰 닭과 작은 닭의 키 차이를 구하는 일을 종암심을 도와 하는 것이다.
매일 GT혹성의 닭들은 알을 낳기 위해 같은 순서로 줄을 선다.
하루는 종암심이 몇마리의 닭들과 닭싸움을 하기로 하였다.
게임을 위해서 현재 줄 선 그룹에서 일련의 몇 마리의 닭을 뽑기로 하였다.
이 게임에서는 뽑은 그룹에서 제일 큰 닭과 작은 닭의 키 차이를 알아야 한다.
종암심은 Q 개의 그룹과 그들의 키들의 리스트를 만들었다.
당신의 일은 각 그룹에서 가장 큰 닭과 작은 닭의 키 차이를 구하는 일을 종암심을 도와 하는 것이다.
첫줄에 두 정수 N, Q ((1 ≤ N ≤ 50,000, 1 ≤ Q ≤ 200,000 인 정수)
다음라인부터 N줄에서 닭들의 키( 1 ≤ 키 ≤ 1,000,000인 정수)
다음 Q줄에는 그룹의 시작과 끝인 A,B(1<=A<=B<=N)가 주어진다.
Q 줄에는 각 (그룹)범위의 최댓값과 최솟값의 차를 출력한다.
6 3
1
7
3
4
2
5
1 5
4 6
2 26
3
01번부터 5번까지의 최댓값은 7이고 최솟값은 1 이므로 6이 정답이다.
4번부터 6번까지의 최댓값은 5이고 최솟값은 2 이므로 3이 정답이다.
2번부터 2번까지의 최댓값은 7이고 최솟값은 7 이므로 0이 정답이다.