CF1793E.Velepin and Marketing
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
The famous writer Velepin is very productive. Recently, he signed a contract with a well-known publication and now he needs to write ki 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 ki 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 aj 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≤n≤3⋅105) — the number of regular readers of Velepin.
The second line contains n integers a1,a2,…,an (1≤ai≤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≤q≤3⋅105) — the number of years to analyze.
Each of the following q lines contains a single integer kj (2≤kj≤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 kj 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.