Description

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.

Input Format

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

Output Format

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

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

2
4
1

Hint

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