Also Try Minecraft

题意翻译

有一个 $1$ 到 $n$ 的序列 $a$，$a_i$ 代表第 $i$ 个格子的高度，若你在 $x$，则你可以走到 $x+1$ 或 $x-1$。若你从一个高为 $p$ 的格子走到一个比它矮的高为 $q$ 格子会受到 $p-q$ 的伤害，若走到一个比它高的格子则不会受到伤害。共 $m$ 组询问，每组询问给出 $s$ 和 $t$，你要求从 $s$ 走到 $t$ 所受到的最少的伤害。

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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.

输入输出样例

输入样例 #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

**题意翻译**

有一个从1到n的序列a，a_i代表第i个格子的高度，若你在x，则你可以走到x+1或x-1。若你从一个高为p的格子走到一个比它矮的高为q的格子会受到p-q的伤害，若走到一个比它高的格子则不会受到伤害。共m组询问，每组询问给出s和t，你要求从s走到t所受到的最少的伤害。

**题目描述**

你正在测试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的跌落伤害，否则你会向上飞行，受到0伤害。

对于每个任务，确定在这个任务过程中可以受到的最小跌落伤害。

**输入输出格式**

**输入格式**

输入的第一行包含两个整数n和m（2≤n≤10^5; 1≤m≤10^5）——世界中的列数和需要测试的任务数。

输入的第二行包含n个整数a_1, a_2, …, a_n（1≤a_i≤10^9），其中a_i是世界第i列的高度。

接下来的m行描述任务。第j行包含两个整数s_j和t_j（1≤s_j, t_j≤n; s_j≠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
```**题意翻译** 有一个从1到n的序列a，a_i代表第i个格子的高度，若你在x，则你可以走到x+1或x-1。若你从一个高为p的格子走到一个比它矮的高为q的格子会受到p-q的伤害，若走到一个比它高的格子则不会受到伤害。共m组询问，每组询问给出s和t，你要求从s走到t所受到的最少的伤害。 **题目描述** 你正在测试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的跌落伤害，否则你会向上飞行，受到0伤害。 对于每个任务，确定在这个任务过程中可以受到的最小跌落伤害。 **输入输出格式** **输入格式** 输入的第一行包含两个整数n和m（2≤n≤10^5; 1≤m≤10^5）——世界中的列数和需要测试的任务数。 输入的第二行包含n个整数a_1, a_2, …, a_n（1≤a_i≤10^9），其中a_i是世界第i列的高度。 接下来的m行描述任务。第j行包含两个整数s_j和t_j（1≤s_j, t_j≤n; s_j≠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 ```