← 返回题目列表

Codeforces · 1793/E

E. Velepin 和营销

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

著名作家Velepin 的作品非常多产。最近,他与一家知名出版社签订了合同,现在他需要在第 $$$i$$$ 年写 $$$k_i$$$ 本书。这对他来说根本不是问题,武士、空间、虚空、昆虫、狼人,他想写多少就写多少。

他有 $$$n$$$ 固定读者,每个人在第 $$$i$$$ 年都会阅读 Velepin 出版的 $$$k_i$$$ 书籍中的一本。读者非常喜欢讨论书籍,所以如果一年内至少有$$$a_j$$$个人和他(包括他自己)读过同一本书,那么$$$j$$$-th就会感到满意。

Velepin 在营销方面存在明显问题,所以他向你求助!一家知名的图书阅读服务可以控制 Velepin 的每个固定读者会阅读的内容,但他不希望书籍被浪费,因此应该有人阅读每本书。因此,他们向您求助,要求您告诉您,如果您可以为每个人选择他要阅读的书,那么每年最多可以满足多少常规读者的需求。

输入

第一行包含一个整数 $$$n$$$ $$$(2 \le n \le 3 \cdot 10^5)$$$ — Velepin 的常规读者数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le n)$$$ — 为了第 $$$i$$$ 人的幸福而需要阅读同一本书的人数。

第三行包含一个整数 $$$q$$$ $$$(1 \le q \le 3 \cdot 10^5)$$$ — 要分析的年数。

以下 $$$q$$$ 行中的每一行都包含一个整数 $$$k_j$$$ $$$(2 \le k_j \le n)$$$ — Velepin 每年必须在 $$$j$$$ 中编写的书籍数量。

输出

打印 $$$q$$$ 行,每一行都只有一个数字——如果 Velepin 发行 $$$k_j$$$ 书籍,每年 $$$j$$$ 可以满足的最大人数。

示例

输入 #1

5
1 2 2 2 2
3
2
3
4

输出 #1

5
5
3

输入 #2

6
1 2 3 4 5 6
2
2
3

输出 #2

5
4

输入 #3

6
4 4 1 4 4 4
3
2
3
4

输出 #3

6
5
1

注意

在第一个示例中,第一年,最佳划分是 $$$1, 2, 2, 2, 2$$$(第一本书由第一个人阅读,其他人阅读第二本书)。第二年,最优解为$$$1,2,2,3,3$$$(第一本书由第一个人阅读,第二本书由第二个人和第三个人阅读,其他人都阅读第三本书)。第三年,最佳分配为 $$$1, 2, 3, 4, 2$$$。因此,多年来满意的人数将为 $$$5, 5, 3$$$。

在第二个例子中,第一年,最优划分是$$$1, 1, 1, 1, 1, 2$$$,那么除了第$$$6$$$之外的每个人都会幸福。第二年,最优分配是$$$1, 1, 1, 1, 2, 3$$$,那么除了第$$$5$$$和第$$$6$$$之外的每个人都会幸福。