Range Spread

Statement

You are given an array of n integers that never changes, and q queries. Each query gives positions l and r (1-indexed, inclusive). For each query print the largest value minus the smallest value among positions l to r.

Input

The first line has n and q. The second line has the n values. Each of the next q lines has l and r.

Output

Print the answer to each query on its own line, in order.

Constraints

1 <= n, q <= 200000
|value| <= 10^9
1 <= l <= r <= n
The difference can be as large as 2 * 10^9, which is close to the limit of a signed 32-bit integer.

Example 1

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

7
7
0

Positions 2..7 have maximum 8 and minimum 1, so 7. A single position always has spread 0.