Description

Every day, Farmer John's N (1 <= N <= 50,000) cows line up in the same sequence.

One day, John decided to let some cows play a frisbee competition. He planned to select a group of cows in consecutive positions in the queue for the competition. However, to avoid significant skill disparities, the height differences among the cows should not be too large.

John prepared Q (1 <= Q <= 180,000) possible selections of cows and recorded the heights of all cows (1 <= height <= 1,000,000). He wants to know the height difference between the tallest and shortest cow in each group.

Note: For the maximum input size, the input and output will occupy most of the runtime.

Input Format

Line 1: N and Q;

Lines 2..N+1: Line i+1 contains the height of the i-th cow;

Lines N+2..N+Q+1: Two integers, A and B (1 <= A <= B <= N), representing all cows from A to B.

Output Format

Lines 1..Q: The answer for each query (the height difference between the tallest and shortest cow in the group), one per line.

```input1 6 3 1 7 3 4 2 5 1 5 4 6 2 2 ``` ```output1 6 3 0 ``` ## Translation

USACO Monthly Contest