CF1700D River Locks

最近在 Divanovo 建造了一套巨大的河流闸门系统。现在有 $n$ 个闸门，第 $i$ 个闸门的容量为 $v_i$ 升，因此它可以容纳 $0$ 到 $v_i$ 升之间的任意水量。每个闸门都连接着一根管道。当管道打开时，每秒会有 $1$ 升水流入该闸门。 该闸门系统的设计方式是：所有超过第 $i$ 个闸门容量的水会立即流向第 $i+1$ 个闸门。如果第 $i+1$ 个闸门也已满，水会继续向后传递。超过最后一个闸门容量的水会流入河流。  上图展示了 $5$ 个闸门，其中第 $1$ 个和第 $3$ 个闸门的管道是开启的。由于第 $1$、$3$、$4$ 个闸门已经被填满，实际上水会流向第 $2$ 和第 $5$ 个闸门。注意，第 $i$ 个闸门的容量可能大于第 $i+1$ 个闸门的容量。 为了让所有闸门都能正常工作，你需要将每一个闸门都完全填满。Divanovo 的市长对 $q$ 个互不相关的询问感兴趣。对于每个询问，假设一开始所有闸门都是空的，所有管道都是关闭的。然后，有一些管道会被同时打开。对于第 $j$ 个询问，市长希望你计算，最少需要打开多少根管道，才能保证所有闸门在不超过 $t_j$ 秒后都被填满。 请帮助市长解决这个棘手的问题，并回答他的所有询问。

第一行包含一个整数 $n$（$1 \le n \le 200\,000$）——闸门的数量。 第二行包含 $n$ 个整数 $v_1, v_2, \dots, v_n$（$1 \le v_i \le 10^9$）——每个闸门的容量。 第三行包含一个整数 $q$（$1 \le q \le 200\,000$）——询问的数量。 接下来的 $q$ 行，每行包含一个整数 $t_j$（$1 \le t_j \le 10^9$）——第 $j$ 个询问中填满所有闸门的时间限制（秒）。

输出 $q$ 个整数，第 $j$ 个数表示在第 $j$ 个询问中，最少需要打开多少根管道，才能保证所有闸门在 $t_j$ 秒内被填满。如果在给定时间内无法填满所有闸门，输出 $-1$。

第一个样例测试中有 $6$ 个询问。 在第 $1, 3, 4$ 个询问中，答案都是 $-1$。即使打开所有管道，也需要等待 $4$ 秒才能填满第一个闸门。 在第 $6$ 个询问中，可以打开第 $1$、$3$ 和 $4$ 个闸门的管道。$4$ 秒后，第 $1$ 和 $4$ 个闸门被填满。在接下来的 $1$ 秒内，$1$ 升水会被传递到第 $2$ 和第 $5$ 个闸门。第 $3$ 个闸门由自己的管道填满。 同理，在第二个询问中，可以打开第 $1$、$3$ 和 $4$ 个闸门的管道。 在第五个询问中，可以打开第 $1, 2, 3, 4$ 个闸门的管道。 由 ChatGPT 4.1 翻译