River Locks

题意翻译

有 $n$ 个容器，第 $i$ 个容器容量为 $v_i$ 升，可以容纳 $[0,v_i]$ 升的水。 满出去的水会将从容器 $i$ 转移到容器 $i+1$，如果 $i+1$ 也满了会转移得更远。满出最后一个容器的水会倒到河中。 现在要将所有容器填满。你可以选择一些容器注水，让这些容器每秒进入一升水。$q$ 次询问，问最初所有容器都是空的，最少选择多少个容器注水使得 $t_i$ 秒内能填满所有容器。 $1\leq n,q\leq 2\times 10^5$，$1\leq v_i,t_i\leq 10^9$。

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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 $ .

输入输出样例

输入样例 #1

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

输出样例 #1

-1
3
-1
-1
4
3

输入样例 #2

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

输出样例 #2

-1
-1
4
4
-1
5

说明

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 $ .

**题意翻译**

有 $n$ 个容器，第 $i$ 个容器容量为 $v_i$ 升，可以容纳 $[0,v_i]$ 升的水。

满出去的水会将从容器 $i$ 转移到容器 $i+1$，如果 $i+1$ 也满了会转移得更远。满出最后一个容器的水会倒到河中。

现在要将所有容器填满。你可以选择一些容器注水，让这些容器每秒进入一升水。$q$ 次询问，问最初所有容器都是空的，最少选择多少个容器注水使得 $t_i$ 秒内能填满所有容器。

$1\leq n,q\leq 2\times 10^5$，$1\leq v_i,t_i\leq 10^9$。

**题目描述**

在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 $ 个整数应该是为了在 $ t_j $ 秒内填满所有锁，需要打开的最少管道数。如果不可能在给定时间内填满所有锁，输出 $ -1 $。**题意翻译** 有 $n$ 个容器，第 $i$ 个容器容量为 $v_i$ 升，可以容纳 $[0,v_i]$ 升的水。 满出去的水会将从容器 $i$ 转移到容器 $i+1$，如果 $i+1$ 也满了会转移得更远。满出最后一个容器的水会倒到河中。 现在要将所有容器填满。你可以选择一些容器注水，让这些容器每秒进入一升水。$q$ 次询问，问最初所有容器都是空的，最少选择多少个容器注水使得 $t_i$ 秒内能填满所有容器。 $1\leq n,q\leq 2\times 10^5$，$1\leq v_i,t_i\leq 10^9$。 **题目描述** 在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 $ 个整数应该是为了在 $ t_j $ 秒内填满所有锁，需要打开的最少管道数。如果不可能在给定时间内填满所有锁，输出 $ -1 $。