您正在测试新的秘密泰拉瑞亚更新。本次更新将为游戏添加任务!
简单来说,世界地图可以表示为长度为 $$$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