Rebrending
Contest: Codeforces Round 852 (Div. 2)
Difficulty rating: 2600
Tags: brute force, data structures, divide and conquer, implementation

Kostya and Zhenya — the creators of the band "Paper" — after the release of the legendary album decided to create a new band "Day movers", for this they need to find two new people.

They invited $$$n$$$ people to the casting. The casting will last $$$q$$$ days. On the $$$i$$$th of the days, Kostya and Zhenya want to find two people on the segment from $$$l_i$$$ to $$$r_i$$$ who are most suitable for their band. Since "Day movers" are doing a modern art, musical skills are not important to them and they look only at other signs: they want the height difference between two people to be as small as possible.

Help them, and for each day, find the minimum difference in the growth of people from the casting on this segment!

Input format:
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 format:
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.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

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$$$).

Example input:
3 3
1 3 2
1 2
2 3
1 3

Example output:
2
1
1

Example input:
5 3
4 1 5 3 2
1 2
3 4
2 4

Example output:
3
2
2

Editorial:
Let's go through all the elements from left to right. The main task will be to support the current version of $$$dp[i]$$$ – the minimum difference of $$$a_i$$$ with the elements to the right of it that we managed to consider. Let us correctly calculate $$$dp$$$ for the first $$$r$$$ elements. Let's move on to $$$r + 1$$$. Let's show how to update the answer for all $$$j < i$$$, such that $$$a[j] > a[i]$$$. For $$$j < i$$$, such that $$$a[j] <a[i]$$$ is solved similarly.
Let's take the first element $$$a[j]$$$ to the left of $$$i$$$, such that $$$a[j] > a[i]$$$. Note that if there is $$$l<j < i$$$ such that $$$a[l] > a[j]> a[i]$$$, then we will not update $$$dp[l]$$$ for it, because $$$|a[l] is a[j]| < |a[l] - a[i]|$$$. Also, we will not update the answer for $$$l$$$ such that $$$|a[l] - a[j]| < |a[l] - a[i]|$$$, that is, if $$$a[l] > a[i] + \frac{a[j] - a[i]}{2}$$$. Therefore, further we will be interested only in the numbers from the segment $$$\left[a[i], a[i] + \frac{a[j] - a[l]}{2}\right]$$$.
Let's note that we have reduced the length of the segment by $$$2$$$ times. That is, there will be no more such iterations than $$$\O(\log n)$$$. You can find the rightmost number belonging to a segment using the segment tree. The answer for the segment $$$l_i, r_i$$$ will be $$$\underset{l_i\leqslant j<r}{\min} dp[l]$$$ at the moment $$$r_i$$$. This can also be efficiently found using the segment tree. The final asymptotics of the solution is $$$\O(n\log^2 n + q\log n)$$$.
There is also a solution for $$$O(n\sqrt(n)+ q\log q)$$$ that passes all the tests.