Velepin and Marketing

题意翻译

著名作家 Velepin 将在接下来的 $q$ 年中第 $i$ 年出版 $k_i$ 本新书，同时有 $n$ 名他的忠实读者，每年都会从 $k_i$ 本新书中选一本阅读。而一年中，如果读者 $j$ 发现有不低于 $a_j$ 个人（包括本身）与他阅读同一本新书，他会感到开心。 给出 $n$ 和 $k$，以及每一年的 $k_i$ 和每一名读者的 $a_j$，求出如果能分配每个读者每年读哪一本书，在保证每一本书都有人读的情况下，每一年开心的读者数量最大值。 $2 \leqslant n \leqslant 3 \cdot 10^5, 1 \leqslant q \leqslant 3 \cdot 10^5, 2 \leqslant k_i \leqslant n, 1 \leqslant a_j \leqslant n$。

题目描述

The famous writer Velepin is very productive. Recently, he signed a contract with a well-known publication and now he needs to write $ k_i $ books for $ i $ -th year. This is not a problem for him at all, he can write as much as he wants about samurai, space, emptiness, insects and werewolves. He has $ n $ regular readers, each of whom in the $ i $ -th year will read one of the $ k_i $ books published by Velepin. Readers are very fond of discussing books, so the $ j $ -th of them will be satisfied within a year if at least $ a_j $ persons read the same book as him (including himself). Velepin has obvious problems with marketing, so he turned to you! A well-known book reading service can control what each of Velepin's regular readers will read, but he does not want books to be wasted, so someone should read each book. And so they turned to you with a request to tell you what the maximum number of regular readers can be made satisfied during each of the years, if you can choose each person the book he will read.

输入输出格式

输入格式

The first line contains a single integer $ n $ $ (2 \le n \le 3 \cdot 10^5) $ — the number of regular readers of Velepin. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ $ (1 \le a_i \le n) $ — the number of necessary readers of the same book for the happiness of the $ i $ -th person. The third line contains a single integer $ q $ $ (1 \le q \le 3 \cdot 10^5) $ — the number of years to analyze. Each of the following $ q $ lines contains a single integer $ k_j $ $ (2 \le k_j \le n) $ — the number of books that Velepin must write in $ j $ -th a year.

输出格式

Print $ q $ lines, each of them has exactly one number — the maximum number of people who can be satisfied in $ j $ -th a year if Velepin releases $ k_j $ books.

输入输出样例

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

说明

In the first example, in the first year, the optimal division is $ 1, 2, 2, 2, 2 $ (the first book is read by the first person, and everyone else reads the second). In the second year, the optimal solution is $ 1, 2, 2, 3, 3 $ (the first book is read by the first person, the second book is read by the second and third person, and all the others read the third book). In the third year, the optimal split will be $ 1, 2, 3, 4, 2 $ . Accordingly, the number of satisfied people over the years will be $ 5, 5, 3 $ . In the second example, in the first year, the optimal division is $ 1, 1, 1, 1, 1, 2 $ , then everyone will be happy except the $ 6 $ -th person. In the second year, the optimal division is $ 1, 1, 1, 1, 2, 3 $ , then everyone will be happy except the $ 5 $ -th and $ 6 $ -th person.

**题意翻译**

著名作家 Velepin 将在接下来的 $ q $ 年中第 $ i $ 年出版 $ k_i $ 本新书，同时有 $ n $ 名他的忠实读者，每年都会从 $ k_i $ 本新书中选一本阅读。而一年中，如果读者 $ j $ 发现有不低于 $ a_j $ 个人（包括本身）与他阅读同一本新书，他会感到开心。

给出 $ n $ 和 $ k $，以及每一年的 $ k_i $ 和每一名读者的 $ a_j $，求出如果能分配每个读者每年读哪一本书，在保证每一本书都有人读的情况下，每一年开心的读者数量最大值。

$ 2 \leqslant n \leqslant 3 \cdot 10^5, 1 \leqslant q \leqslant 3 \cdot 10^5, 2 \leqslant k_i \leqslant n, 1 \leqslant a_j \leqslant n $。

**题目描述**

The famous writer Velepin is very productive. Recently, he signed a contract with a well-known publication and now he needs to write $ k_i $ books for $ i $-th year. This is not a problem for him at all, he can write as much as he wants about samurai, space, emptiness, insects, and werewolves.

He has $ n $ regular readers, each of whom in the $ i $-th year will read one of the $ k_i $ books published by Velepin. Readers are very fond of discussing books, so the $ j $-th of them will be satisfied within a year if at least $ a_j $ persons read the same book as him (including himself).

Velepin has obvious problems with marketing, so he turned to you! A well-known book reading service can control what each of Velepin's regular readers will read, but he does not want books to be wasted, so someone should read each book. And so they turned to you with a request to tell you what the maximum number of regular readers can be made satisfied during each of the years, if you can choose each person the book he will read.

**输入输出格式**

**输入格式**

第一行包含一个整数 $ 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 $ 本书，那么在这一年可以满足的最大人数。**题意翻译** 著名作家 Velepin 将在接下来的 $ q $ 年中第 $ i $ 年出版 $ k_i $ 本新书，同时有 $ n $ 名他的忠实读者，每年都会从 $ k_i $ 本新书中选一本阅读。而一年中，如果读者 $ j $ 发现有不低于 $ a_j $ 个人（包括本身）与他阅读同一本新书，他会感到开心。 给出 $ n $ 和 $ k $，以及每一年的 $ k_i $ 和每一名读者的 $ a_j $，求出如果能分配每个读者每年读哪一本书，在保证每一本书都有人读的情况下，每一年开心的读者数量最大值。 $ 2 \leqslant n \leqslant 3 \cdot 10^5, 1 \leqslant q \leqslant 3 \cdot 10^5, 2 \leqslant k_i \leqslant n, 1 \leqslant a_j \leqslant n $。 **题目描述** The famous writer Velepin is very productive. Recently, he signed a contract with a well-known publication and now he needs to write $ k_i $ books for $ i $-th year. This is not a problem for him at all, he can write as much as he wants about samurai, space, emptiness, insects, and werewolves. He has $ n $ regular readers, each of whom in the $ i $-th year will read one of the $ k_i $ books published by Velepin. Readers are very fond of discussing books, so the $ j $-th of them will be satisfied within a year if at least $ a_j $ persons read the same book as him (including himself). Velepin has obvious problems with marketing, so he turned to you! A well-known book reading service can control what each of Velepin's regular readers will read, but he does not want books to be wasted, so someone should read each book. And so they turned to you with a request to tell you what the maximum number of regular readers can be made satisfied during each of the years, if you can choose each person the book he will read. **输入输出格式** **输入格式** 第一行包含一个整数 $ 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 $ 本书，那么在这一年可以满足的最大人数。