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 disparities in skill levels, the heights of the cows should not differ too much.

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

Note: For the largest data set, 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 to each query (the difference between the tallest and shortest cow in the specified range), 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