CF1709B.Also Try Minecraft

You are beta testing the new secret Terraria update. This update will add quests to the game!

Simply, the world map can be represented as an array of length $n$, where the $i$-th column of the world has height $a_i$.

There are $m$ quests you have to test. The $j$-th of them is represented by two integers $s_j$ and $t_j$. In this quest, you have to go from the column $s_j$ to the column $t_j$. At the start of the quest, you are appearing at the column $s_j$.

In one move, you can go from the column $x$ to the column $x-1$ or to the column $x+1$. In this version, you have Spectre Boots, which allow you to fly. Since it is a beta version, they are bugged, so they only allow you to fly when you are going up and have infinite fly duration. When you are moving from the column with the height $p$ to the column with the height $q$, then you get some amount of fall damage. If the height $p$ is greater than the height $q$, you get $p - q$ fall damage, otherwise you fly up and get $0$ damage.

For each of the given quests, determine the minimum amount of fall damage you can get during this quest.

你正在对《泰拉瑞亚》（Terraria）的新秘密更新进行 Beta 测试。该更新将为游戏加入任务系统！

简而言之，世界地图可表示为一个长度为 $n$ 的数组，其中第 $i$ 列的高度为 $a_i$。

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

每次移动，你可以从第 $x$ 列移动到第 $x-1$ 列或第 $x+1$ 列。本版本中，你装备了“幽灵靴”（Spectre Boots），允许你飞行。但由于这是 Beta 版本，该装备存在 Bug：它仅允许你在向上移动时飞行，且飞行持续时间无限。当你从高度为 $p$ 的列移动到高度为 $q$ 的列时，你会受到一定量的坠落伤害。若 $p > q$，则你受到 $p - q$ 点坠落伤害；否则（即 $p \leq q$），你向上飞行，不受到任何伤害。

对于每个给定的任务，请计算你在完成该任务过程中所能承受的最小坠落伤害总量。

The first line of the input contains two integers $n$ and $m$ ($2 \le n \le 10^5; 1 \le m \le 10^5$) — the number of columns in the world and the number of quests you have to test, respectively.

The second line of the input contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the height of the $i$-th column of the world.

The next $m$ lines describe quests. The $j$-th of them contains two integers $s_j$ and $t_j$ ($1 \le s_j, t_j \le n; s_j \ne t_j$), which means you have to move from the column $s_j$ to the column $t_j$ during the $j$-th quest.

Note that $s_j$ can be greater than $t_j$.

输入的第一行包含两个整数 $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$。

Print $m$ integers. The $j$-th of them should be the minimum amount of fall damage you can get during the $j$-th quest completion.

输出 $m$ 个整数。其中第 $j$ 个整数应为完成第 $j$ 次任务过程中所能受到的最小坠落伤害值。