题目描述

小明和 $n$ 个选手正在参加一个“天梯”游戏，每个选手都有一个积分，选手的积分按严格递增顺序排列，即：

小明初始不在这 $n$ 个选手中。现在小明想通过“挑战”来提升自己的排名。
每次挑战，小明会从积分比他高的选手中选择积分最低的一个进行挑战。挑战规则如下：

• 小明的积分增加 $1$；
• 被挑战选手的积分减少 $1$。

共有 $q$ 次询问。每次询问给出小明的初始积分 $x$，以及他想达到的目标排名 $y$（按当前积分排名，并列视为同名次），你需要求出小明至少需要多少次挑战才能达到该排名。

输入格式

第一行包含两个整数 $n$ 和 $q$ （$1 \leq n, q \leq 2 \times 10^5$），表示选手数量和询问次数；

第二行包含 $n$ 个严格递增的整数 $a_1, a_2, \ldots, a_n$ （$1 \leq a_i \leq 10^9$），表示每个选手的初始积分；

接下来 $q$ 行，每行两个整数 $x$ 和 $y$ （$0 \leq x \leq 10^9,\ 1 \leq y \leq n+1$），分别表示小明的初始积分和目标排名。

输出格式

对于每次询问，在一行中输出一个整数，表示小明至少需要多少次挑战才能达到目标排名。

输入输出样例 #1

输入 #1

5 3
2 5 8 11 20
25 1
3 4
0 2

输出 #1

0
1
9

输入输出样例 #2

输入 #2

2 3
2 3
1 3
1 2
1 1

输出 #2

0
1
2