Level Up
Contest: Educational Codeforces Round 168 (Rated for Div. 2)
Difficulty rating: 2200
Tags: binary search, brute force, data structures, divide and conquer, implementation

Monocarp is playing a computer game. He starts the game being level $$$1$$$. He is about to fight $$$n$$$ monsters, in order from $$$1$$$ to $$$n$$$. The level of the $$$i$$$-th monster is $$$a_i$$$.

For each monster in the given order, Monocarp's encounter goes as follows:

- if Monocarp's level is strictly higher than the monster's level, the monster flees (runs away);
- otherwise, Monocarp fights the monster.

After every $$$k$$$-th fight with a monster (fleeing monsters do not count), Monocarp's level increases by $$$1$$$. So, his level becomes $$$2$$$ after $$$k$$$ monsters he fights, $$$3$$$ after $$$2k$$$ monsters, $$$4$$$ after $$$3k$$$ monsters, and so on.

You need to process $$$q$$$ queries of the following form:

- $$$i~x$$$: will Monocarp fight the $$$i$$$-th monster (or will this monster flee) if the parameter $$$k$$$ is equal to $$$x$$$?

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the number of monsters and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — the levels of the monsters.

In the $$$j$$$-th of the following $$$q$$$ lines, two integers $$$i$$$ and $$$x$$$ ($$$1 \le i, x \le n$$$) — the index of the monster and the number of fights required for a level up in the $$$j$$$-th query.

Output format:
For each query, output "YES", if Monocarp will fight the $$$i$$$-th monster in this query, and "NO", if the $$$i$$$-th monster flees.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Example input:
4 16
2 1 2 1
1 1
2 1
3 1
4 1
1 2
2 2
3 2
4 2
1 3
2 3
3 3
4 3
1 4
2 4
3 4
4 4

Example output:
YES
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES

Example input:
7 15
1 1 2 1 1 1 1
5 3
2 2
2 2
1 6
5 1
5 5
7 7
3 5
7 4
4 3
2 5
1 2
5 6
4 1
6 1

Example output:
NO
YES
YES
YES
NO
YES
YES
YES
NO
NO
YES
YES
YES
NO
NO

Editorial:
I would like to describe two different intended solutions to this problem.
Solution One.
Let's start with the following idea. How many times can the character's level increase for a fixed $$$k$$$? Given that there are $$$n$$$ monsters, even if we fight all of them, the level will not exceed $$$\frac{n}{k}$$$. That is, if we sum over all $$$k$$$, the level will change no more than $$$O(n \log n)$$$ times (harmonic series).
Let's simulate the process for each $$$k$$$ and find out when the level changed. Suppose the character's level became $$$x$$$ after fighting monster $$$i$$$. Then the level will become $$$x + 1$$$ after fighting the $$$k$$$-th monster with a level greater than or equal to $$$x$$$ after position $$$i$$$. That is, if we had an array of positions of monsters with a level greater than or equal to $$$x$$$, we could find the position of the level change from it. Unfortunately, it is not possible to keep all such arrays in memory.
Instead, let's try to use a more powerful data structure. Now, suppose we want to add or remove positions from the structure and be able to query the $$$k$$$-th position greater than $$$i$$$. Such structures exist. We can use a segment tree, a BIT, or an ordered_set from pbds.
How can we reduce the problem to using this structure? The idea is as follows. Previously, we had the idea to iterate over $$$k$$$ and inside that iterate over the current character level. Let's do the opposite. We will iterate over the character level on the outside. And inside, we will update the level for all such $$$k$$$ for which the character has not reached the end of the monsters yet.
It turns out that this will be a prefix of the $$$k$$$. Why is that? For each $$$x$$$, the character reaches level $$$x$$$ at some $$$k$$$ no later than at $$$k + 1$$$. Suppose this is not the case. Consider the first such $$$x$$$ where the character reached level $$$x$$$ at $$$k$$$ later than at $$$k + 1$$$. That is, he reached level $$$x - 1$$$ earlier or at the same time. This means that he will encounter at least all the same monsters at $$$k$$$ as at $$$k + 1$$$ (since the segment of monsters will start no later and end no earlier). Since at $$$k + 1$$$, the character must have encountered at least $$$k + 1$$$ monsters of level at least $$$x$$$, at $$$k$$$ he will definitely encounter at least $$$k$$$. Thus, this cannot happen.
Then the implementation is as follows. For each $$$k$$$, we will maintain the position at which the character reached the current level $$$x$$$. Then, for the prefix of $$$k$$$, for which this position is within the array, we will update it with the new position for level $$$k + 1$$$. For this, we will store the positions of all monsters of level at least $$$x$$$ in the data structure. After processing level $$$x$$$, we will remove all monsters of this level from the structure. To find the new position, we need to make such queries to the structure: either find the $$$k$$$-th position after the current saved one (in the segment tree or Fenwick tree), or find the first (using order_of_key) and move $$$k - 1$$$ positions from it (using find_by_order) (in ordered_set).
We can answer the queries within the simulation. For each $$$k$$$, we will store all queries related to it and sort them in ascending order of $$$i$$$. Since within each $$$k$$$ we move in the order of increasing level, and thus position, we can answer the queries in that order. While the position of the query is less than or equal to the position where the level will become $$$x + 1$$$, we answer the queries by checking that the monster's level at that position is not less than $$$x$$$.
Overall complexity: $$$O(n \log^2 n)$$$.
Solution Two.
Let's still simulate level increases directly.
We will use the square root heuristics. If $$$k$$$ is greater than or equal to some constant $$$B$$$, then the character will definitely fight all monsters of level at least $$$\frac{n}{B}$$$, simply because he cannot become greater than this level himself. That is, if we choose $$$B$$$ on the order of $$$1000$$$, for example, we only need to know whether the character is fighting a monster, only for monsters of level no higher than $$$200$$$.
We will solve the problem for all $$$k$$$ less than $$$1000$$$ in $$$O(n)$$$. That is, we will honestly go through the monsters, maintaining the character's level and a counter of fights until the level increases.
For larger $$$k$$$, we will solve the problem as follows. We will sum the indices of all characters of each level from $$$1$$$ to $$$200$$$ into separate arrays. We will consider whom the character fought at the end of the game for each level separately. It is obvious that for each level of monsters $$$x$$$, the character fought a prefix of these monsters. Since the character's level increases monotonically, at some point the character's level will exceed $$$x$$$, and all monsters of level $$$x$$$ will flee.
Moreover, if the character fought a monster for some $$$k$$$, he will also fight it for $$$k + 1$$$ (by the proof from the previous solution).
Thus, to find out which new monsters the character will fight at level $$$k$$$, we can do the following. We will iterate over monster levels up to $$$200$$$ and for the first fleeing monster of this level, we will check whether the character will fight it now. For this, we need to find out how many monsters the character fought before this monster. If his level is not less than this number divided by $$$k$$$ (rounded down), then he will fight it. Among all the first monsters the character will fight, we will find the minimum. For it, our solution is definitely correct. For the others, this is not necessarily true, because the character's level may increase due to fights to the left of this position.
If no such monsters are found, then for this $$$k$$$ we have found all. Otherwise, in some data structure, we will mark that the character is fighting with the leftmost found monster.
Thus, we need a data structure that can answer prefix sum queries and update an element at a certain position. There are quite a few such structures. However, we have a large number of queries: for each fight, we need to make $$$200$$$ queries, that is, a total of $$$n \cdot 200$$$ queries. However, there are not so many updates: each position will be updated in the structure no more than once, that is, no more than $$$n$$$ updates. Therefore, we would like to have a structure that balances these operations. For example, let the query be $$$O(1)$$$, and the update be $$$O(\sqrt{n})$$$.
We will divide the array into blocks of size $$$O(\sqrt{n})$$$. For each block, we will store the sum of elements up to its left boundary. And for each position within each block, we will store the sum up to the left boundary of the block. Then, to query the prefix sum up to $$$i$$$, we need to add the sum up to the left position of the block $$$\frac{i}{\sqrt{n}}$$$ and the sum from $$$i$$$ to the start of this block. To update at position $$$i$$$, we need to add one to the first sum for each block from $$$\frac{i}{\sqrt{n}} + 1$$$ to the end. And also for each position from $$$i$$$ to the end of its block.
Queries can be answered as follows. For each monster, we will keep track of the first $$$k$$$ at which we will fight it. Then it is sufficient to check that the $$$k$$$ from the query is not less than this value.
Overall complexity: $$$O(n \sqrt{n})$$$.