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