Problem E: 平均身高

Problem E: 平均身高

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 13  Solved: 3
[Submit] [Status] [Web Board] [Creator:]

Description

FJ 的 N头牛总是按同一序列排队。有一天,FJ 决定让一些牛玩一场飞盘比赛。他准备找一群在对列中为置连续的牛来进行比赛,但是为了避免水平悬殊,牛的身高不应该相差太大。FJ 准备了Q 个可能的牛的选择和所有牛的身高。他想知道每一组里面最高和最低的牛的身高差别。


FJ’s N cows always line up in the same sequence. One day, FJ decided to let some cows play a frisbee game. He is going to find a group of cows that are consecutively placed in the opposite row to compete, but in order to avoid the disparity in level, the height of the bulls should not be too different. FJ prepared Q possible choices of cows and the heights of all cows. He wanted to know the difference in height between the tallest and lowest cows in each group.


Input

第一行,NQ
第二行至第N+1行,第i+1行是第i头牛的身高hi
第N+2至第N+Q+1行,每行两个整数AB,表示从AB的所有牛


The first line, N and Q

The second line to the N+1th line, the i+1th line is the height h(i) of the i-th cow

Lines N+2 to N+Q+1, each line contains two integers A and B, representing all cows from A to B

Output

第一至第Q行,每行一个整数,表示对于询问的回答(即最高和最低的牛的身高差)。


From the first to the Qth line, each line has an integer, which represents the answer to the query (that is, the height difference between the tallest and shortest cow).


Sample Input Copy

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

Sample Output Copy

6
3
0

HINT

对于全部数据, 1 <= N <= 5* 104,  1 <= Q <= 1.8*105,1<=hi<=106, 1<=A<=B<=N

For all data, 1 <= N <= 5* 104, 1 <= Q <= 1.8*105, 1<=hi<=106, 1<=A<=B<=N