Making Football Teams

RamprosadG Replay of BSMRSTU Home Qu...
Limits 2s, 512 MB

There are N football teams and each team has a positive number of players. You are given Q queries.

Query: Given two integers X and K. You are given K extra players, and you can add any number of players in any team from these extra players. You have to find the maximum number of football teams can be formed so that every team has at least X players.

Every query is independent.

Input

The first line contains an integer $N$ ($1 \le N \le 5 \times 10^5$), the number of teams. The next line contains $N$ integers, the number players in each team ($1 \le C_i \le 10^9$).

The next line contains an integer $Q$ ($1 \le Q \le 5 \times 10^5$), the number of queries. The next Q lines contain two integers each, $X$ ($1 \le X \le 10^9$) and $K$ ($0 \le K \le 10^{15}$).

Output

For each query, print the maximum number of teams that can be formed.

Sample

InputOutput
5
1 5 2 3 7
2
10 3
10 8
1
2

Submit

Login to submit.

Statistics

62% Solution Ratio
prodip_bsmrstuEarliest, May '20
prodip_bsmrstuFastest, 0.3s
EgorKulikovLightest, 9.6 MB
MursaleenShortest, 691B
Toph uses cookies. By continuing you agree to our Cookie Policy.