Description

Original problem from USACO 2007 Jan. Gold

FJ's $N$ cows always line up in the same sequence. One day, FJ decided to let some cows play a frisbee game. He plans to select a group of cows standing in a continuous segment of the line for the competition. However, to avoid significant differences in skill levels, the heights of the cows should not vary too much. FJ has prepared $Q$ possible groups of cows and the heights of all cows. He wants to know the difference between the tallest and shortest cows in each group.

Input Format

The first line contains $N$ and $Q$;
The second to the $(N+1)$-th lines, the $(i+1)$-th line contains the height $h_i$ of the $i$-th cow;
The $(N+2)$-th to the $(N+Q+1)$-th lines each contain two integers $A$ and $B$, representing the range of cows from $A$ to $B$.

Output Format

The first to the $Q$-th lines each contain an integer, representing the answer to the query (i.e., the difference between the tallest and shortest cows in the group).

Sample 1

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

6
3
0

Data Range and Hints

For all data, $1\le N\le 5\times 10^4$, $1\le Q\le 1.8\times 10^5$, $1\le h_i\le 10^6$, $1\le A\le B\le N$.