CF1793E Velepin and Marketing

著名作家 Velepin 非常高产。最近，他与一家知名出版机构签订了合同，现在他需要在第 $i$ 年写出 $k_i$ 本书。这对他来说毫无压力，他可以随意写关于武士、太空、虚无、昆虫和狼人等题材的书。 他有 $n$ 位固定读者，每位读者在第 $i$ 年会阅读 Velepin 出版的 $k_i$ 本书中的一本。读者们非常喜欢讨论书籍，因此第 $j$ 位读者如果在一年内有至少 $a_j$ 个人（包括他自己）阅读了同一本书，他就会感到满意。 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 在第 $j$ 年出版 $k_j$ 本书，最多能有多少人感到满意。

在第一个样例中，第一年最优分配为 $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$ 个人外，其他人都满意。 由 ChatGPT 4.1 翻译