Hard_problem — OOI qualification
Task type: batch | Time limit: 1 s | Memory limit: 256 MB | Difficulty: 24
Algorithms: number theory, data structures, sorting, binary search

# Hard problem

| Input file:   | standard input  |
|---------------|-----------------|
| Output file:  | standard output |
| Time limit:   | 1 second        |
| Memory limit: | 256 megabytes   |

The boy Gena loves solving complex programming problems very much. Recently, he created a collection of $n$ problems that he plans to solve. The problems have difficulty levels $a_1, a_2, ..., a_n$ and it is known that the difficulty levels of any two problems are different.

Gena is a very experienced programmer and can solve problems of any difficulty. He solves problems daily, following a specific strategy.

For each day, Gena has a fixed parameter $m$ — the minimum difficulty level of the problems he is willing to solve. Every day, Gena goes through all the problems in his collection starting from the first to the last, and for each problem, he does the following action:

- If the current problem has already been solved, he skips it and moves on to the next one.
- If the difficulty level of the current problem is less than $m$, he skips it and moves on to the next one.
- If the previous conditions are not met and he has not solved any problems on the current day, he solves the current problem and moves on to the next one.
- If the previous conditions are not met and the last problem solved on the current day was easier than the current problem, he solves the current problem and moves on to the next one.
- If none of the previous conditions are met, Gena skips the problem and moves on to the next one.

In other words, Gena solves the problems in increasing order of difficulty every day, but only solves problems that he hasn't solved before and are of difficulty level greater than or equal to $m$.

On the first day, the minimum difficulty of the problems he is ready to solve is equal to $t$, and each subsequent day he will decrease $m$ by the value of $s$. Thus, on the $i$-th day (starting from 1), Gena is ready to solve problems with difficulty level not less than $t - s \cdot (i - 1)$. Gena will repeat the algorithm described above daily until he solves all the problems.

The boy Lesha has been observing Gena's successes for a long time and wants to know the secret of his problem-solving strategy. Therefore, Lesha has $q$ queries. For each query, it is required to check whether it is possible to rearrange the problems in Gena's selection so that he can solve the problem with difficulty level $d_i$ as the $p_i$-th problem among all the problems solved on all days. Help Lesha answer all his queries.

Note that the queries are independent, meaning that different orders of problems can be used for different queries in Gena's selection.

#### Input

The first line contains three integers $n$, $t$ and $s$ ($1 \le n \le 200000$, $1 \le t, s \le 10^9$) — the number of problems in the selection, the minimum difficulty level on the first day, and the step of decreasing the difficulty level of the problems.

The second line contains $n$ distinct integers $a_1, a_2, ..., a_n$ ($1 \le a_i \le 10^9$, $a_i < a_{i+1}$) — the difficulty levels of the problems.

The third line contains a single integer $q$ ($1 \le q \le 200000$) — the number of queries.

Each of the next $q$ lines contains two integers $d_i$ and $p_i$ ($1 \le p_i \le n$) — the parameters of the query: can the problems in the selection be rearranged so that the problem with difficulty level $d_i$ is solved as the $p_i$-th problem. It is guaranteed that for each query, there exists a problem in the selection whose difficulty level is equal to $d_i$.

#### Output

For each query, print «Yes» (without quotes) if it is possible to rearrange the problems in the selection in a way that satisfies the query condition, and «No» (without quotes) otherwise.

#### Examples

| standard input  | standard output |
|-----------------|-----------------|
| 5 10 2          | Yes             |
| 4 5 9 10 12     | Yes             |
| 5               | No              |
| 10 2            | Yes             |
| 10 3            | Yes             |
| 10 4            | No              |
| 5 5             | No              |
| 12 2            | Yes             |
| 7 4 2           | Yes             |
| 2 3 5 6 9 10 11 | No              |
| 4               | Yes             |
| 5 6             | Yes             |
| 11 7            | No              |
| 2 2             | No              |
| 10 7            | Yes             |

#### Note

Let's consider the first example and suppose that for the first query we can rearrange the problems in the selection in the following order: 12, 4, 5, 9, 10. Then Gena will solve the problems as follows:

1. On the first day, the minimum difficulty of the problems $m = 10$. The first problem in the selection satisfies this condition. Gena will solve it immediately. Among the remaining problems, there is a problem with difficulty 10, but since Gena has already solved a problem with difficulty 12 on the first day, he will skip the problem with difficulty 10. Thus, at the end of the first day, Gena will have solved only the problem with difficulty 12.
2. On the second day, the minimum difficulty of the problems $m = 8$. While going through the problems in the selection, Gena will skip problem 12 as he has already solved it. He will also skip problems 4 and 5, as their difficulty is less than $m$. Then he will encounter a problem with difficulty 9, and since he hasn't solved any problems on the second day yet, he will solve it. The next problem is of difficulty 10, and since its difficulty is greater than the difficulty of the last problem solved on that day, he will solve it. Thus, after the first two days, Gena will have solved the problems with difficulty 12, 9, 10 in that order.
3. On the third day, Gena will not solve any problems, as all the problems with difficulty at least $m = 6 = 10 - 2 \cdot 2$ have already been solved.
4. On the last fourth day, Gena will solve the remaining problems. In the end, he will have solved the problems with difficulty 12, 9, 10, 4, 5 in that order over all the days.

With the given rearrangement of tasks in the set, Gena will solve a task of difficulty 9 second in the order among all. Therefore, the answer to the first query is «Yes».

#### Scoring

The tests for this problem consist of 8 groups. Points for each group are awarded only if all the tests in that group and some tests from the previous groups pass.

| Group | Score | Additional constraints |   |    |   | Required groups | Comment    |
|-------|-------|------------------------|---|----|---|-----------------|------------|
|       |       | $n$                    | $q$ | $a_i$ | $t$ |                 |            |
| 0     | 0     | -                      | -   | -     | -   | -               | Samples.   |
| 1     | 13    | $n \le 8$              | -   | $a_i \le 10$ | $t \le 10$ | -               |            |
| 2     | 10    | $n \le 8$              | -   | -     | -   | 0, 1            |            |
| 3     | 14    | $n \le 500$            | -   | -     | $t \le 10$ | 0, 1            |            |
| 4     | 19    | $n \le 500$            | -   | -     | -   | 0 - 3           |            |
| 5     | 9     | -                      | $q = 1$ | -     | -   | -               |            |
| 6     | 1     | -                      | -   | -     | $t = 1$   | -               |            |
| 7     | 9     | -                      | -   | -     | -   | -               | $s = 10^9$ |
| 8     | 25    | -                      | -   | -     | -   | 0 - 7           |            |

Starter code: