题目描述

徐老师每天晚上都做同一个梦，他总是梦见自己是邪恶世界的一位勇士，登上邪恶世界最高的恶魔塔救出美丽的公主，然后过上幸福的生活。

恶魔塔共有 $n$ 层，每一层都有一个恶魔守护，其战力由古老的恶魔之力决定。为了成功攀登恶魔塔（击败第 $n$ 层的恶魔守护）救出公主，徐老师必须一层层地挑战恶魔守护，每一层的恶魔守护战力为 $a_i$。只有当挑战者的战力 严格大于 恶魔守护的战力时，才能击败它们，继续前进。挑战一次恶魔守护会耗费 $1$ 点时间，并且挑战成功后会获得 $1$ 点战力提升。如果遇到无法击败的恶魔守护，徐老师可以选择花费 $1$ 点时间来修炼，每次修炼后会获得 $1$ 点战力提升。

徐老师想知道，以 $m$ 种不同的初始战力 $b_i$，从不同的起点 $s_i$ 开始挑战时，成功攀登的最短时间。

输入格式

输入的第一行包含一个正整数 $n$ 和一个正整数 $m$，表示恶魔塔的层数和挑战的数量。

第二行包含 $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$