K. Known Problem
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Here comes a well-known problem,

Given an integer sequence $$$a_1, a_2, \ldots, a_N$$$. The task is to respond to $$$Q$$$ queries that seek the smallest value among the absolute differences of all pairs of elements within a specified range $$$[l_i, r_i]$$$.

This problem has appeared in various online judges, including TIOJ 1905, Codeforces 765F, Codeforces 1793F, and even CS Academy Closest Numbers. Why do we still need to solve this problem?

Let us present an advanced version of it. In this version, we provide $$$Q$$$ queries for a given integer sequence $$$a_1, a_2, \ldots, a_N$$$, where each query asks to find the second smallest value among the absolute differences of all pairs of elements within a specified range $$$[l_i, r_i]$$$.

In this context, the second smallest value within a multiset $$$S$$$ is determined as the minimum value $$$v$$$, for which there are at least two elements in $$$S$$$ that are not greater than $$$v$$$.

Input

The input begins with two integers $$$N$$$ and $$$Q$$$, denoting the length of the sequence and the number of operations, respectively.

The second line contains $$$N$$$ integers $$$a_1, a_2, \ldots, a_N$$$, representing the elements of the initial sequence.

Following that, $$$Q$$$ lines are provided, each containing two integers $$$l_i$$$ and $$$r_i$$$, representing the $$$i$$$-th query.

  • $$$3 \leq N \leq 10^5$$$
  • $$$1 \leq Q \leq 3\times 10^6$$$
  • $$$0 \leq a_i \leq 10^9$$$
  • $$$1 \leq l_i, r_i \leq N$$$
  • $$$r_i - l_i \gt 1$$$
Output

For each query, output the second smallest difference within the range $$$[l_i, r_i]$$$.

Example
Input
6 6
3 1 4 1 5 3
1 3
3 5
1 5
1 4
2 5
4 6
Output
2
3
1
1
1
2
Note

As you can see, the time limit is tight since $$$Q$$$ can be up to $$$3\times 10^6$$$. Therefore, it is advisable to avoid extensive use of slow data structures like std::map, std::unordered_map, etc.