题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

一支带有力量 $P$ 的箭从数轴上的位置 0 向右方发射。在每个整数位置 $i$ ($1 \le i \le N$)，最多可以设置一个防御力为 $D_i$ 的干草堆。

当箭撞到干草堆时，如果箭的力量小于或等于该干草堆的防御力，箭会立即停止。反之，如果箭的力量大于防御力，箭的力量会减去 $D_i$，然后穿过干草堆继续飞行。

对于两个整数 $X, P$，我们将 $f(X, P)$ 的值定义为“为了使力量为 $P$ 的箭在位置 $X$ 或其左侧停止所需要安装的干草堆的最小数量”。如果无论如何安装都无法使箭停止，则定义 $f(X, P) = -1$。

请编写一个程序，对于 $Q$ 个整数对 $(X_j, P_j)$ ($1 \le j \le Q$)，分别求出 $f(X_j, P_j)$ 的值。

输入格式

第一行给定可以安装干草堆的位置数量 $N$ 和发射的箭的数量 $Q$，以空格分隔。

第二行给定可以在位置 $i$ ($1 \le i \le N$) 放置的干草堆的防御力 $D_1, D_2, \cdots, D_N$，以空格分隔。

从第三行开始的 $Q$ 行，给出 $Q$ 个整数对。其中第 $j$ ($1 \le j \le Q$) 行给定 $X_j$ 和 $P_j$，以空格分隔。

输出格式

输出 $Q$ 行。其中第 $j$ ($1 \le j \le Q$) 行输出 $f(X_j, P_j)$ 的值。

5 6
2 5 6 1 12
1 1
5 14
2 8
3 7
4 14
5 1

1
2
-1
2
4
1

5 5
3 6 1 1 10
1 10
2 10
3 10
4 10
5 10

-1
-1
3
3
1

提示

限制条件

• 给定的所有数都是整数。
• $1 \le N, Q \le 300,000$
• 对于每个 $1 \le i \le N$ 的 $i$，都有 $1 \le D_i \le 10^9$。
• 对于每个 $1 \le j \le Q$ 的 $j$，都有 $1 \le X_j \le N$。
• 对于每个 $1 \le j \le Q$ 的 $j$，都有 $1 \le P_j \le 10^9$。

子任务

1. (6 分) $N, Q \le 18$。
2. (16 分) $N, Q \le 5000$。
3. (18 分) 对于所有 $1 \le i \le N$ 的 $i$，$D_i \le 300$。
4. (32 分) 对于所有 $1 \le i < N$ 的 $i$，$D_i \le D_{i+1}$。
5. (28 分) $N=Q$，且对于所有 $1 \le j \le Q$ 的 $j$，$X_j=j$，且 $P_1 = P_2 = \cdots = P_Q$。
6. (16 分) 对于所有 $1 \le j \le Q$ 的 $j$，$X_j = N$。
7. (12 分) 对于所有 $1 \le i < j \le N$ 的 $i, j$，$D_i \ne D_j$。
8. (22 分) 无附加限制条件。