题目描述

你正在为全新的秘密 Terraria 更新进行测试。本次更新将为游戏添加任务系统！

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

你需要测试 $m$ 个任务。第 $j$ 个任务由两个整数 $s_j$ 和 $t_j$ 表示。在这个任务中，你需要从第 $s_j$ 列移动到第 $t_j$ 列。任务开始时，你出现在第 $s_j$ 列。

每次移动，你可以从第 $x$ 列移动到第 $x-1$ 列或第 $x+1$ 列。在这个版本中，你拥有 Spectre Boots，可以让你飞行。但由于是测试版，这双靴子有 bug，只能在你向上移动时飞行，并且飞行时间无限。当你从高度为 $p$ 的列移动到高度为 $q$ 的列时，你会受到一定的摔落伤害。如果 $p > q$，你会受到 $p-q$ 的摔落伤害，否则你会飞上去，不会受到伤害。

对于每个任务，请你计算在完成该任务过程中你能获得的最小摔落伤害。

输入格式

第一行包含两个整数 $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$ 个任务所能获得的最小摔落伤害。

说明/提示

由 ChatGPT 4.1 翻译

样例

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

2
10
0
7
3
1