CF1793F Rebrending

Kostya 和 Zhenya 是乐队 “Paper” 的创始人，在发行了传奇专辑后，他们决定组建一个新乐队 “Day movers”。为此，他们需要再找两个人。 他们邀请了 $n$ 个人来参加选拔。选拔将持续 $q$ 天。在第 $i$ 天，Kostya 和 Zhenya 想在区间 $l_i$ 到 $r_i$ 之间找到两位最适合乐队的人。由于 “Day movers” 追求现代艺术，音乐技能对他们来说并不重要，他们只关注其他特征：他们希望两个人的身高差尽可能小。 请帮助他们，对于每一天，找出该区间内两个人的最小身高差！

第一行包含两个整数 $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 < r_i \leq n$），表示第 $i$ 天选拔的区间。

输出 $q$ 行。第 $i$ 行输出第 $i$ 天选拔区间内两位候选人身高的最小差值。

在第一个样例中，区间 $[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$）。 由 ChatGPT 4.1 翻译