Kostya和Zhenya - 乐队“Paper”的创作者 - 在发行传奇专辑后决定创建一个新乐队“Day movers”,为此他们需要找到两个新人。
他们邀请了 $$$n$$$ 人参加选角。选角将持续 $$$q$$$ 天。在 $$$i$$$ 日,Kostya 和 Zenya 希望在 $$$l_i$$$ 到 $$$r_i$$$ 段中找到最适合他们乐队的两个人。由于“白日搬家”从事的是现代艺术,所以音乐技巧对他们来说并不重要,他们只看其他标志:他们希望两个人之间的身高差尽可能小。
帮助他们,每一天,找出该片段选角中人物成长的最小差异!
输入
在第一行中,您会得到两个整数 $$$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
3 3 1 3 2 1 2 2 3 1 3
输出 #1
2 1 1
输入 #2
5 3 4 1 5 3 2 1 2 3 4 2 4
输出 #2
3 2 2
输入 #3
7 4 2 6 1 7 3 5 4 4 6 1 2 3 6 1 3
输出 #3
2 4 2 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$$$) 构成。