CF1700D.River Locks

Recently in Divanovo, a huge river locks system was built. There are now $n$ locks, the $i$-th of them has the volume of $v_i$ liters, so that it can contain any amount of water between $0$ and $v_i$ liters. Each lock has a pipe attached to it. When the pipe is open, $1$ liter of water enters the lock every second.

The locks system is built in a way to immediately transfer all water exceeding the volume of the lock $i$ to the lock $i + 1$. If the lock $i + 1$ is also full, water will be transferred further. Water exceeding the volume of the last lock pours out to the river.

The picture illustrates $5$ locks with two open pipes at locks $1$ and $3$. Because locks $1$, $3$, and $4$ are already filled, effectively the water goes to locks $2$ and $5$.

Note that the volume of the $i$-th lock may be greater than the volume of the $i + 1$-th lock.

To make all locks work, you need to completely fill each one of them. The mayor of Divanovo is interested in $q$ independent queries. For each query, suppose that initially all locks are empty and all pipes are closed. Then, some pipes are opened simultaneously. For the $j$-th query the mayor asks you to calculate the minimum number of pipes to open so that all locks are filled no later than after $t_j$ seconds.

Please help the mayor to solve this tricky problem and answer his queries.

最近，迪瓦诺沃市建成了一套庞大的船闸系统。目前共有 $n$ 座船闸，其中第 $i$ 座船闸的容积为 $v_i$ 升，因此它可容纳 $0$ 到 $v_i$ 升之间的任意水量。每座船闸均连接有一根进水管。当某根进水管开启时，每秒向对应船闸注入 $1$ 升水。

该船闸系统的设计使得：一旦第 $i$ 座船闸中的水量超过其容积 $v_i$，超出部分将立即流入第 $i+1$ 座船闸；若第 $i+1$ 座船闸也已满，则水继续向后传递；最终，超出最后一座船闸容积的水量将直接溢入河流。

图中展示了 $5$ 座船闸，其中第 $1$ 和第 $3$ 座船闸的进水管处于开启状态。由于第 $1$、$3$ 和 $4$ 座船闸已满，水实际上流入了第 $2$ 和第 $5$ 座船闸。

注意：第 $i$ 座船闸的容积可能大于第 $i+1$ 座船闸的容积。

为使所有船闸正常运行，必须将每座船闸完全注满。迪瓦诺沃市长提出了 $q$ 个相互独立的询问。对每个询问，假设初始状态下所有船闸均为空且所有进水管均关闭，然后同时开启若干进水管。对于第 $j$ 个询问，市长希望你计算：为确保所有船闸在 $t_j$ 秒内（含）全部注满，至少需要开启多少根进水管。

请帮助市长解决这一难题，并回答他的所有询问。

The first lines contains one integer $n$ ($1 \le n \le 200\,000$) — the number of locks.

The second lines contains $n$ integers $v_1, v_2, \dots, v_n$ ($1 \le v_i \le 10^9$)) — volumes of the locks.

The third line contains one integer $q$ ($1 \le q \le 200\,000$) — the number of queries.

Each of the next $q$ lines contains one integer $t_j$ ($1 \le t_j \le 10^9$) — the number of seconds you have to fill all the locks in the query $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$ 次查询中用于填满所有锁的时间（单位：秒）。

Print $q$ integers. The $j$-th of them should be equal to the minimum number of pipes to turn on so that after $t_j$ seconds all of the locks are filled. If it is impossible to fill all of the locks in given time, print $-1$.

输出 $q$ 个整数。其中第 $j$ 个整数应等于：使得所有锁在 $t_j$ 秒后均被注满所需的最少开启管道数量。若在给定时间内无法注满所有锁，则输出 $-1$。

There are $6$ queries in the first example test.

In the queries $1, 3, 4$ the answer is $-1$. We need to wait $4$ seconds to fill the first lock even if we open all the pipes.

In the sixth query we can open pipes in locks $1$, $3$, and $4$. After $4$ seconds the locks $1$ and $4$ are full. In the following $1$ second $1$ liter of water is transferred to the locks $2$ and $5$. The lock $3$ is filled by its own pipe.

Similarly, in the second query one can open pipes in locks $1$, $3$, and $4$.

In the fifth query one can open pipes $1, 2, 3, 4$.

第一个样例测试中有 $6$ 个查询。

在第 $1$、$3$、$4$ 个查询中，答案为 $-1$。即使我们打开所有管道，也需要等待 $4$ 秒才能将第一个闸室注满。

在第六个查询中，我们可以打开位于闸室 $1$、$3$ 和 $4$ 的管道。经过 $4$ 秒后，闸室 $1$ 和 $4$ 被注满。接下来的 $1$ 秒内，有 $1$ 升水被输送到闸室 $2$ 和 $5$。闸室 $3$ 则由其自身的管道注满。

类似地，在第二个查询中，可以打开位于闸室 $1$、$3$ 和 $4$ 的管道。

在第五个查询中，可以打开位于闸室 $1$、$2$、$3$ 和 $4$ 的管道。