As a student, you're probably lazy. Realizing that, jsumabat has decided to decrease the word length of this problem and to keep it simple:

Given an array ~N~ with ~Q~ subarray queries, you are to find the maximum and minimum values of the subarrays, and output the difference of the two.

Note: Solutions that are unintended and pass will result in an attempt of jsumabat to create a test case that fails your solution.

Constraints

~1 \le N \le 10^4~

~1 \le Q \le 10^5~

~1 \le a_i \le b_i \le N~

The values of the array are positive integers that can be up to ~10^9~.

Input Specification

The first line contains two integers, ~N~ and ~Q~.

The next line contains ~N~ integers, representing the values of the array in order (from ~1~ to ~N~).

The last ~Q~ lines will contain two integers, ~a_i~ and ~b_i~, the 1-indexed query.

Output Specification

For each query, output the maximum number in the subarray - the minimum number in the subarray.

Sample Input 1

6 4
1 3 9 4 3 5
1 2
2 5
4 6
4 5

Sample Output 1

2
6
2
1