Rebrending

Description:

Input:

In the first line you are given two integers $$$n$$$ and $$$q$$$ ($$$2 \leq n \leq 3 \cdot 10^5, 1 \leq q \leq 10^6$$$) — the number of people who came to the casting and the number of casting days.

In the second line, you are given $$$n$$$ integers $$$a_1, a_2, a_3, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — the growth of each of the candidates.

It is also guaranteed that all $$$a_i$$$ are different.

The following $$$q$$$ lines each contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \leq l_i < r_i \leq n$$$) — a segment of people on the $$$i$$$th day of casting.

Output:

Output $$$q$$$ lines. In the $$$i$$$-th line there should be a minimum height difference between the two candidates on the segment on the $$$i$$$-th day of casting.

Sample Input:

3 3
1 3 2
1 2
2 3
1 3

Sample Output:

2
1
1

Sample Input:

5 3
4 1 5 3 2
1 2
3 4
2 4

Sample Output:

3
2
2

Sample Input:

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

Sample Output:

2
4
2
1

Note:

In the first example, the minimum difference on the segment $$$[1, 2]$$$ is $$$2$$$, on the segment $$$[2, 3]$$$ — $$$1$$$, on the segment $$$[1, 3]$$$ is also $$$1$$$.

In the third example, the numbers with the minimum difference on the segment $$$[4, 6]$$$ are $$$3$$$ and $$$5$$$ ($$$5 - 3 = 2$$$). On the segment $$$[1, 2]$$$, the numbers with the minimum difference are $$$2$$$ and $$$6$$$ ($$$6 - 2 = 4$$$). On the segment $$$[3, 6]$$$, the numbers with the minimum difference are $$$1$$$ and $$$3$$$ ($$$3 - 1 = 2$$$). On the segment $$$[1, 3]$$$, the minimum difference is formed by the numbers $$$1$$$ and $$$2$$$ ($$$2 - 1 = 1$$$).