P5926 [JSOI2009] The Interview Test

For each query, find the absolute difference between two numbers in the given interval that are the closest to each other and are not equal. **Note: “Closest” means closest in value.**

The first line contains two integers $N, Q$, representing the length of the sequence and the number of queries. The second line contains $N$ positive integers separated by spaces, representing the entire sequence, numbered from left to right as $A_1, A_2, \ldots, A_N$. The next $Q$ lines each contain two integers $i, j$, representing a query interval. The input guarantees that $1 \le i < j \le N$.

For each query, output one line: the absolute difference between the two closest (and unequal) numbers in the queried interval.

For $100\%$ of the data, $1 \le N, Q \le 10^5$, $1 \le A_i \le 10^9$. The testdata is generated entirely **purely at random**. Translated by ChatGPT 5