第 3 题 干草堆 (haystack)

时间限制 1.0 s · 空间限制 256 MB · 112 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 haystack.in，输出文件 haystack.out。

题目描述

从数轴的坐标 0 处向右发射一支具有整数大小力量的箭。在每个整数坐标 $i$（$1 \le i \le N$）上，最多可以放置一个防御力为 $D_i$ 的干草堆。

当箭撞到干草堆时，若箭的力量小于或等于防御力，则箭立即停下；反之，若箭的力量大于防御力，则力量先减少 $D_i$，然后箭穿透干草堆继续飞行。

对于两个整数 $X, P$，定义 $f(X, P)$ 为“为了使力量为 $P$ 的箭在坐标 $X$ 处或坐标 $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

输入：

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

样例 2

输入：

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$。
• 对所有 $i$（$1 \le i \le N$），$1 \le D_i \le 10^9$。
• 对所有 $j$（$1 \le j \le Q$），$1 \le X_j \le N$。
• 对所有 $j$（$1 \le j \le Q$），$1 \le P_j \le 10^9$。

子任务

1. （6 分）$N, Q \le 18$。
2. （16 分）$N, Q \le 5\,000$。
3. （18 分）对所有 $i$（$1 \le i \le N$），$D_i \le 300$。
4. （32 分）对所有 $i$（$1 \le i < N$），$D_i \le D_{i+1}$。
5. （28 分）$N = Q$，且对所有 $j$（$1 \le j \le Q$），$X_j = j$，$P_1 = P_2 = \cdots = P_Q$。
6. （16 分）对所有 $j$（$1 \le j \le Q$），$X_j = N$。
7. （12 分）对所有 $i < j$（$1 \le i < j \le N$），$D_i \neq D_j$。
8. （22 分）无附加约束。