CF1793F.Rebrending

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!

科斯佳和热尼亚——乐队“Paper”的创始人——在发布传奇专辑后，决定组建一支新乐队“Day movers”，为此他们需要招募两名新成员。

他们邀请了 $n$ 个人参加试镜。试镜将持续 $q$ 天。在第 $i$ 天，科斯佳和热尼亚希望在区间 $[l_i, r_i]$ 内选出两人，使其最符合乐队的要求。由于“Day movers”致力于现代艺术，音乐技能对他们而言并不重要，他们只关注其他特征：他们希望所选两人的身高差尽可能小。

请帮助他们，对每一天，求出该区间内所有试镜者身高的最小差值！

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 \lt r_i \leq n$) — a segment of people on the $i$th day of casting.

第一行给出两个整数 $n$ 和 $q$（$2 \leq n \leq 3 \cdot 10^5$，$1 \leq q \leq 10^6$）—— 分别表示参加试镜的人数和试镜天数。

第二行给出 $n$ 个整数 $a_1, a_2, a_3, \ldots, a_n$（$1 \leq a_i \leq n$）—— 表示每位候选人的身高。

同时保证所有 $a_i$ 互不相同。

接下来的 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \lt r_i \leq n$）—— 表示第 $i$ 天试镜的人员区间。

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.

输出 $q$ 行。第 $i$ 行应为第 $i$ 天选角时，该区间内两名候选人之间的最小身高差。

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

在第一个例子中，区间 $[1, 2]$ 上的最小差值为 $2$，区间 $[2, 3]$ 上为 $1$，区间 $[1, 3]$ 上同样为 $1$。

在第三个例子中，区间 $[4, 6]$ 上差值最小的两个数是 $3$ 和 $5$（$5 - 3 = 2$）；区间 $[1, 2]$ 上差值最小的两个数是 $2$ 和 $6$（$6 - 2 = 4$）；区间 $[3, 6]$ 上差值最小的两个数是 $1$ 和 $3$（$3 - 1 = 2$）；区间 $[1, 3]$ 上的最小差值由数字 $1$ 和 $2$ 构成（$2 - 1 = 1$）。