← 返回题目列表

Codeforces · 1709/B

B. 也尝试一下我的世界

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

您正在测试新的秘密泰拉瑞亚更新。本次更新将为游戏添加任务!

简单来说,世界地图可以表示为长度为 $$$n$$$ 的数组,其中世界的第 $$$i$$$ 列的高度为 $$$a_i$$$。

有 $$$m$$$ 任务需要测试。其中第 $$$j$$$ 由两个整数 $$$s_j$$$ 和 $$$t_j$$$ 表示。在此任务中,您必须从 $$$s_j$$$ 列转到 $$$t_j$$$ 列。在任务开始时,您会出现在 $$$s_j$$$ 列中。

一次,您可以从 $$$x$$$ 列转到 $$$x-1$$$ 列或 $$$x+1$$$ 列。在此版本中,您拥有幽灵靴,可以让您飞行。由于它是测试版,所以它们有窃听器,所以它们只允许你在上升时飞行,并且有无限的飞行时间。当您从高度为 $$$p$$$ 的柱子移动到高度为 $$$q$$$ 的柱子时,您会受到一定程度的坠落伤害。如果高度 $$$p$$$ 大于高度 $$$q$$$,你会受到 $$$p - q$$$ 坠落伤害,否则你会飞起来并受到 $$$0$$$ 伤害。

对于每个给定的任务,确定您在此任务中可以获得的最小坠落伤害。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 10^5; 1 \le m \le 10^5$$$) - 分别是世界中的列数和你必须测试的任务数。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是世界第 $$$i$$$ 列的高度。

接下来的 $$$m$$$ 行描述任务。其中第 $$$j$$$ 包含两个整数 $$$s_j$$$ 和 $$$t_j$$$ ($$$1 \le s_j, t_j \le n; s_j \ne t_j$$$),这意味着在第 $$$j$$$ 任务期间,您必须从 $$$s_j$$$ 列移动到 $$$t_j$$$ 列。

请注意,$$$s_j$$$ 可以大于 $$$t_j$$$。

输出

打印 $$$m$$$ 整数。其中第 $$$j$$$ 应该是您在完成第 $$$j$$$ 任务期间可以获得的最低坠落伤害。

示例

输入 #1

7 6
10 8 9 6 8 12 7
1 2
1 7
4 6
7 1
3 5
4 2

输出 #1

2
10
0
7
3
1