← 返回题目列表

Codeforces · 1700/D

D. 河闸

中文机器翻译题面 查看原题

最近在迪瓦诺沃修建了一个巨大的河闸系统。现在有$$$n$$$个锁,其中第$$$i$$$的容积为$$$v_i$$$升,因此它可以容纳$$$0$$$到$$$v_i$$$升之间的任意数量的水。每个锁上都附有一根管子。当管道打开时,每秒 $$$1$$$ 升水进入水闸。

船闸系统的构建方式是立即将所有超过船闸 $$$i$$$ 容量的水转移到船闸 $$$i + 1$$$。如果锁 $$$i + 1$$$ 也满了,水将进一步转移。超过最后一个水闸容量的水倾泻到河流中。

该图展示了 $$$5$$$ 锁,$$$1$$$ 和 $$$3$$$ 锁处有两个打开的管道。由于水闸 $$$1$$$、$$$3$$$ 和 $$$4$$$ 已注满,因此水实际上流向水闸 $$$2$$$ 和 $$$5$$$。

请注意,第 $$$i$$$ 锁的交易量可能大于第 $$$i + 1$$$ 锁的交易量。

要使所有锁都工作,您需要完全填充每一个锁。迪瓦诺沃市长对 $$$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$$$。

示例

输入 #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

注意

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

在查询 $$$1, 3, 4$$$ 中,答案是 $$$-1$$$。即使我们打开所有管道,我们也需要等待 $$$4$$$ 秒来填充第一个锁。

在第六个查询中,我们可以打开锁 $$$1$$$、$$$3$$$ 和 $$$4$$$ 中的管道。 $$$4$$$ 秒后,锁 $$$1$$$ 和 $$$4$$$ 已满。在接下来的$$$1$$$第二个$$$1$$$升水被转移到水闸$$$2$$$和$$$5$$$。锁 $$$3$$$ 由其自己的管道填充。

类似地,在第二个查询中,可以打开锁 $$$1$$$、$$$3$$$ 和 $$$4$$$ 中的管道。

在第五个查询中,可以打开管道 $$$1, 2, 3, 4$$$。