매일 존의 소들은 젖을 짜기 위해 같은 순서로 줄을 선다.(1 ≤ N ≤ 50,000) 하루는 존이 몇마리의 소들과 Ultimate Frisbee 게임을 하기로 하였다.

게임을 위해서 현재 줄 선 그룹에서 일련의 몇 명을 뽑기로 하였다. 이 게임에서는 뽑은 그룹에서 제일 큰 소와 작은 소의 키 차이를 알아야 한다.

존은 Q 개의 그룹과 그들의 키들의 리스트를 만들었다. Q (1 ≤ Q ≤ 200,000) (1 ≤ 키 ≤ 1,000,000)

당신의 일은 각 그룹에서 가장 큰 소와 작은 소의 키 차이를 구하는 일을 존을 도와 하는 것이다.

입력

• 두 개의 정수 N , Q
• 다음 라인부터 N 줄에는 소들의 키가 주어지고
• 다음 Q 줄에는 A , B (1 ≤ A ≤ B ≤ N) 가 주어진다. 범위는 A , B 를 포함

출력

입출력 예

입력

6 3
1
7
3
4
2
5
1 5
4 6
2 2

출력

6
3
0

권장

출처: USACO 2007 January Silver