P13514 [KOI 2025 #1] 干草堆

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

一支带有力量 $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)$ 的值。

### 限制条件 * 给定的所有数都是整数。 * $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 分) 无附加限制条件。