Making Football Teams

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

5
1 5 2 3 7
2
10 3
10 8

1
2