A15690 | Velepin and Marketing

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.