### 题目描述 $n$ 层妖塔是一座有 $n$ 层的妖塔。当然，这是废话。 最下面是第 $1$ 层，最上面是第 $n$ 层，每一层都有一个守护者，第 $i$ 层的守护者的战力是 $a_i$。当且仅当挑战者的战力**严格大于**守护者的战力时，才可以将其击败。挑战者击败第 $i$ 层的守护者后可以前往第 $i+1$ 层，当战胜第 $n$ 层的挑战者后，视为挑战成功。 挑战一次守护者会耗费一点时间，并且挑战成功后会获得一点战力提升。如果挑战者无法击败该层守护者，挑战者可以选择花费一点时间来修炼，每次修炼后会获得一点战力提升。 但是守护者的战力并不是越高层越强大，并且挑战者也并不一定是从第 $1$ 层开始挑战。 现在，有 $m$ 个挑战者，第 $i$ 个挑战者的战力为 $b_i$，其开始挑战的层数为 $s_i$。请你计算出每一名挑战者挑战成功所需要花费的最短时间。 ### 输入格式 第一行输入两个整数，表示 $n$ 和 $m(0\le n,m\le 10^5)$。 第二行有 $n$ 个整数，表示 $a(0\le a\le 10^{10})$。 接下来 $m$ 行，每行两个整数，表示 $b$ 和 $s(0 \le b \le 10^{10},0\le s\le n)$。 ### 输出格式 输出共 $m$ 行，第 $i$ 行表示第 $i$ 个挑战者的最短耗时。 ### 样例输入 ``` 5 3 4 5 6 9 8 3 1 2 2 3 4 ``` ### 样例输出 ``` 9 10 9 ``` ### 说明/提示 对于第一个战力为 $2$ 从第一层开始的挑战者： 花费 $1$ 点时间击败第一层，战力变为 $3$。 由于无法击败第二层，所以花费 $1$ 点时间修炼，战力变为 $4$。花费 $1$ 点时间击败第二层，战力变为 $5$。 花费 $1$ 点时间击败第三层，战力变为 $6$。 由于无法击败第四层，花费 $2$ 点时间修炼，战力变为 $8$。花费 $1$ 点时间击败第四层，战力变为 $9$。 花费 $1$ 点时间击败第五层，战力变为 $10$。 共花费了 $8$ 点时间。