← 返回题目列表

Codeforces · 1793/F

F. 重新设计

中文机器翻译题面 查看原题

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$$$) 构成。