最近在迪瓦诺沃修建了一个巨大的河闸系统。现在有$$$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$$$。