"What's the Time, Mr. Fox?" (狐狸先生幾多點) is a popular children's game in Hong Kong. In this chase/tag-styled game, $$$N$$$ players cautiously approach the tagger, Mr. Fox, before desperately trying to avoid being caught.
Today, you are participating in a "What's the Time, Mr. Fox?" game with $$$N$$$ friends. You will be playing as Mr. Fox, while your friends will be the $$$N$$$ players trying to avoid being caught by you. The game is played on a track of length $$$L$$$, where point 0 is the origin, and point $$$L$$$ is the destination. All $$$N$$$ players are initially positioned at point 0, while you are initially positioned at point $$$L$$$. The $$$i$$$-th player ($$$1 \leq i \leq N$$$) has a pace of $$$A_i$$$.
It is guaranteed that $$$1 \leq A_1 \lt A_2 \lt \dots \lt A_N \leq L$$$, and $$$A_{i+1} - A_i \geq A_{i+2} - A_{i+1}$$$ for $$$1 \leq i \leq N - 2$$$.
The players' goal is to reach the destination or avoid being caught by you, while your goal is to catch as many players as possible.
The game proceeds as follows:
If a player has not walked a distance of at least $$$L$$$ in the first stage, and reached point 0 strictly after the time you reached point 0 in the second stage, that player is considered caught by you. (In other words, any player that is not safe is caught by you.)
Given $$$Q$$$ scenarios, where in the $$$i$$$-th scenario, you are provided with the integers $$$P$$$ and $$$W$$$, the players' running speed and your running speed in the second stage respectively, determine, with the optimal choice of the real number $$$U$$$ (such $$$U$$$ may not be unique), what is the maximum number of players that you can possibly catch.
The first line contains three integers $$$N$$$, $$$L$$$, and $$$Q$$$ ($$$1 \leq N, Q \leq 2 \times 10^5$$$, $$$1 \leq L \leq 10^9$$$), representing the number of players (not counting you), the length of the track, and the number of scenarios respectively.
The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$, representing the pace of the players. You are reminded that $$$1 \leq A_1 \lt A_2 \lt \dots \lt A_N \leq L$$$ and $$$A_{i+1} - A_i \geq A_{i+2} - A_{i+1}$$$ for $$$1 \leq i \leq N - 2$$$.
The next $$$Q$$$ lines each contain two integers $$$P$$$ and $$$W$$$ ($$$1 \leq P \lt W \leq 10^9$$$), representing the parameters for a scenario.
For each scenario, output one integer, the maximum number of players that you can possibly catch.
4 70 11 2 3 442 69
2
Sample 1:
By choosing 22 as $$$U$$$, we can catch player 2 and 3.
| Название |
|---|


