Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Making Football Teams!!!

By RamprosadG · Limits 2s, 512 MB

There are N football teams and each team has 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 made so that every team has at least X players.

Note: Every query is independent.

Input

First line contains N(1 ≤ N ≤ 5 × 105), the number of teams.
Next line contains N integers, the number players in each team(1 ≤ number of players ≤ 109).
Next line contains an integer Q(1 ≤ Q ≤ 5 × 105), the number of query.
Next Q line contains two integers X(1 ≤ X ≤ 109) and K(0 ≤ K ≤ 1015).

Output

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

Sample

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

Discussion

Statistics


67% Solution Ratio

prodip_bsmrstuEarliest, 1M ago

prodip_bsmrstuFastest, 0.3s

EgorKulikovLightest, 9.6 MB

YouKnowWhoShortest, 715B

Submit

Login to submit