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.
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
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).
6 3
1
7
3
4
2
5
1 5
4 6
2 2
6
3
0
For all data, 1
<= N <= 5* 104, 1 <= Q <= 1.8*105, 1<=hi<=106,
1<=A<=B<=N