2760: T4 柚子塔
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：9
解决：0
题目描述
Moc 是柚子世界的一位勇士，他一直梦想着攀登那传说中的柚子塔。
柚子塔共有 $n$ 层，每一层都有一个守护者，其战力由古老的柚子之力决定。为了成功攀登柚子塔（击败第 $n$ 层的守护者），Moc 必须一层层地挑战守护者，每一层的守护者战力为 $a_i$。只有当挑战者的战力 **严格大于** 守护者的战力时，才能击败它们，继续前进。挑战一次守护者会耗费 $1$ 点时间，并且挑战成功后会获得 $1$ 点战力提升。如果遇到无法击败的守护者，Moc 可以选择花费 $1$ 点时间来修炼，每次修炼后会获得 $1$ 点战力提升。
Moc 想知道，以 $m$ 种不同的初始战力 $b_i$，从不同的起点 $s_i$ 开始挑战时，成功攀登的最短时间。
柚子塔共有 $n$ 层，每一层都有一个守护者，其战力由古老的柚子之力决定。为了成功攀登柚子塔（击败第 $n$ 层的守护者），Moc 必须一层层地挑战守护者，每一层的守护者战力为 $a_i$。只有当挑战者的战力 **严格大于** 守护者的战力时，才能击败它们，继续前进。挑战一次守护者会耗费 $1$ 点时间，并且挑战成功后会获得 $1$ 点战力提升。如果遇到无法击败的守护者，Moc 可以选择花费 $1$ 点时间来修炼，每次修炼后会获得 $1$ 点战力提升。
Moc 想知道，以 $m$ 种不同的初始战力 $b_i$，从不同的起点 $s_i$ 开始挑战时，成功攀登的最短时间。
输入
输入的第一行包含一个正整数 $n$ 和一个正整数 $m$，表示柚子塔的层数和挑战的数量。
第二行包含 $n$ 个用空格分隔的正整数，第 $i$ 个数 $a_i$ 表示第 $i$ 层守护者的战力。
接下来 $m$ 行，每行包含两个正整数 $b_i, s_i$，表示第 $i$ 次挑战的初始战力和开始挑战的层数。
第二行包含 $n$ 个用空格分隔的正整数，第 $i$ 个数 $a_i$ 表示第 $i$ 层守护者的战力。
接下来 $m$ 行，每行包含两个正整数 $b_i, s_i$，表示第 $i$ 次挑战的初始战力和开始挑战的层数。
输出
输出包含 $m$ 行，每行一个正整数，表示从每个起点成功攀登柚子塔的最短时间。
样例输入 复制
5 2
1 3 3 7 5
2 1
1 2样例输出 复制
8
9提示
- 对于前 $10\%$ 的数据，$n, m \le 20$
- 对于前 $30\%$ 的数据，$n, m \le 10000$
- 对于 $100\%$ 的数据，$1 \le n, m \le 100000$，$1 \leq a_i, b_i, s_i \leq n$
- 对于前 $30\%$ 的数据，$n, m \le 10000$
- 对于 $100\%$ 的数据，$1 \le n, m \le 100000$，$1 \leq a_i, b_i, s_i \leq n$