Two Sequences
Contest: Hello 2022
Difficulty rating: 3500
Tags: data structures, hashing, string suffix structures

Consider an array of integers $$$C = [c_1, c_2, \ldots, c_n]$$$ of length $$$n$$$. Let's build the sequence of arrays $$$D_0, D_1, D_2, \ldots, D_{n}$$$ of length $$$n+1$$$ in the following way:

- The first element of this sequence will be equals $$$C$$$: $$$D_0 = C$$$.
- For each $$$1 \leq i \leq n$$$ array $$$D_i$$$ will be constructed from $$$D_{i-1}$$$ in the following way:   Let's find the lexicographically smallest subarray of $$$D_{i-1}$$$ of length $$$i$$$. Then, the first $$$n-i$$$ elements of $$$D_i$$$ will be equals to the corresponding $$$n-i$$$ elements of array $$$D_{i-1}$$$ and the last $$$i$$$ elements of $$$D_i$$$ will be equals to the corresponding elements of the found subarray of length $$$i$$$.

Array $$$x$$$ is subarray of array $$$y$$$, if $$$x$$$ can be obtained by deletion of several (possibly, zero or all) elements from the beginning of $$$y$$$ and several (possibly, zero or all) elements from the end of $$$y$$$.

For array $$$C$$$ let's denote array $$$D_n$$$ as $$$op(C)$$$.

Alice has an array of integers $$$A = [a_1, a_2, \ldots, a_n]$$$ of length $$$n$$$. She will build the sequence of arrays $$$B_0, B_1, \ldots, B_n$$$ of length $$$n+1$$$ in the following way:

- The first element of this sequence will be equals $$$A$$$: $$$B_0 = A$$$.
- For each $$$1 \leq i \leq n$$$ array $$$B_i$$$ will be equals $$$op(B_{i-1})$$$, where $$$op$$$ is the transformation described above.

She will ask you $$$q$$$ queries about elements of sequence of arrays $$$B_0, B_1, \ldots, B_n$$$. Each query consists of two integers $$$i$$$ and $$$j$$$, and the answer to this query is the value of the $$$j$$$-th element of array $$$B_i$$$.

Input format:
The first line contains the single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the length of array $$$A$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — the array $$$A$$$.

The third line contains the single integer $$$q$$$ ($$$1 \leq q \leq 10^6$$$) — the number of queries.

Each of the next $$$q$$$ lines contains two integers $$$i$$$, $$$j$$$ ($$$1 \leq i, j \leq n$$$) — parameters of queries.

Output format:
Output $$$q$$$ integers: values of $$$B_{i, j}$$$ for required $$$i$$$, $$$j$$$.

Constraints:
Time limit: 8.0 s
Memory limit: 256.0 MB

Note:
In the first test case $$$B_0 = A = [2, 1, 3, 1]$$$.

$$$B_1$$$ is constructed in the following way:

- Initially, $$$D_0 = [2, 1, 3, 1]$$$.
- For $$$i=1$$$ the lexicographically smallest subarray of $$$D_0$$$ of length $$$1$$$ is $$$[1]$$$, so $$$D_1$$$ will be $$$[2, 1, 3, 1]$$$.
- For $$$i=2$$$ the lexicographically smallest subarray of $$$D_1$$$ of length $$$2$$$ is $$$[1, 3]$$$, so $$$D_2$$$ will be $$$[2, 1, 1, 3]$$$.
- For $$$i=3$$$ the lexicographically smallest subarray of $$$D_2$$$ of length $$$3$$$ is $$$[1, 1, 3]$$$, so $$$D_3$$$ will be $$$[2, 1, 1, 3]$$$.
- For $$$i=4$$$ the lexicographically smallest subarray of $$$D_3$$$ of length $$$4$$$ is $$$[2, 1, 1, 3]$$$, so $$$D_4$$$ will be $$$[2, 1, 1, 3]$$$.
- So, $$$B_1 = op(B_0) = op([2, 1, 3, 1]) = [2, 1, 1, 3]$$$.

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

Example output:
2
1
1
3

Editorial:
Let's denote the construction of array $$$D_i$$$ from array $$$D_{i-1}$$$ as the $$$i$$$-th step of transformation $$$op$$$. Also let's behave as all steps affect $$$C$$$ instead of creating multiple new arrays.
The solution consists of $$$4$$$ parts:
1. Show that there exists small $$$m$$$, such that $$$B_m = B_{m-1}$$$. If $$$n \leq 10^5$$$ then $$$m$$$ doesn't exceed $$$7$$$ ($$$m = \mathcal{O}(\log\log n)$$$).
2. Find the lexicographically smallest suffix for each prefix of some array.
3. For subarray $$$c_l, \ldots, c_r$$$ find the smallest $$$k$$$ such that the subarray $$$c_l, \ldots, c_r$$$ is a period (without a prefix) of the subarray $$$c_k, \ldots, c_r$$$. Show that on the $$$(n-r+1)$$$-th step of transformation the lexicographically smallest subarray starts in $$$c_l$$$ or in $$$c_k$$$.
4. Find the way to simulate the transformation quite fast.
Total time complexity is $$$\mathcal{O}(n \log^2 n \log\log n)$$$.
You can try to solve each of the parts independently!
Part $$$1$$$.
Let's concider an array $$$C$$$ we are going to apply $$$op$$$ to. It is easy to see that $$$op(C) = C$$$ if it is non-increasing (because on each step the suffix of length $$$i$$$ will be one of the lexicographically smallest subarrays of length $$$i$$$).
Otherwise let $$$j$$$ be the smallest index such that $$$c_j < c_{j+1}$$$. Let $$$x$$$ be the smallest index such that $$$c_x = c_j$$$ (then $$$c_x = c_{x+1} = \ldots = c_j$$$, all element of the subarray of length $$$j - x + 1$$$ are equal). The first $$$n - j - 1$$$ steps doesn't affect the prefix of length $$$j + 1$$$. It is easy to see that the last $$$x$$$ steps doesn't change array (the reason is the same as in the paragraph above).
Let's understand what happends on the $$$(n-j)$$$-th step. We should find the lexicographically smallest subarray that starts on the prefix of length $$$j+1$$$. The smallest element on this prefix is $$$c_j$$$, thus this subarray will start in one of positions between $$$x$$$ and $$$j$$$. Since $$$c_j < c_{j+1}$$$ the subarray of length $$$n-j$$$ that starts in the position $$$x$$$ is always one of the lexicographically smallest subarrays.
Thus after the $$$(n-j)$$$-th step
• If $$$x + n - j - 1 \leq j$$$, then all elements on positions between $$$j+1$$$ and $$$n$$$ became equals to $$$c_x$$$ (because the selected subarray constists only of elements that are equal $$$c_x$$$). It it easy to see that array becomes non-increasing so it won't ever change again.
• Otherwise elements on positions $$$j+1, j+2, \ldots, j+(j-x-1)$$$ becomes equal $$$c_x$$$ and elements on positions $$$j+(j-x), \ldots, n$$$ are equal to old values of $$$c_x, c_{x+1}, \ldots, c_{n-(j-x)}$$$. By the way $$$c_{j+(j-x)}$$$ is equal to the old value of $$$c_x$$$.
It is important that in the second case the length of the subarray of the equal elements becomes $$$(j-x+1)+(j-x+1)$$$ and it is followed by the greater element.
Now we can apply the same ideas to the steps between the $$$(n-j+1)$$$-th and $$$(n-x)$$$-th. We see that the length of the subarray filled by the same elements becomes $$$(j-x+1) + (j-x+1) + (j-x) + (j-x-1) + \ldots + 1 = \frac{(j-x+3)(j-x+2)}{2}-1$$$ or this subarray becomes the suffix and whole array won't change again.
In the initial array $$$A$$$ the length of this subarray (the subarray of the equal elements starting at position $$$x$$$) is at least $$$1$$$, so
• in $$$B_1$$$ it is at least $$$2$$$,
• in $$$B_2$$$ it is at least $$$5$$$,
• in $$$B_3$$$ it is at least $$$20$$$,
• in $$$B_4$$$ it is at least $$$230$$$,
• in $$$B_5$$$ it is at least $$$26795$$$,
• in $$$B_6$$$ this subarray becomes the suffix. After that all arrays will be equal $$$B_6$$$ (because $$$n \leq 10^5$$$).
The integers above are connected with the sequence A007501.
Now we know that we should simulate $$$op$$$ only $$$6$$$ times to get all answers. In the following solution I will optimize $$$op$$$ assuming that time limit is aproximately $$$1$$$ sec. It is easy to see how to find $$$B_6$$$ in linear time and simulate $$$op$$$ only $$$5$$$ times.
Part $$$2$$$.
If we had no change queries than the problem is to find the lexicographically smallest substring of length $$$k$$$ in the given string for all $$$k$$$ between $$$1$$$ and $$$n$$$. The solution of this problem is building the suffix array and finding the lexicographically smallest suffix of length at least $$$k$$$.
It is important that change queries change the suffix of the initial array to "something lexicographically small". And that on the $$$i$$$-th step the required substring starts in one of position on the prefix of length $$$i-1$$$. We can guess that we should find the lexicographically smallest suffix of each prefix. I will prove that it is almost enough later.
As far as I know it is not the well known problem so I will describe the solution.
At first we can build the suffix array of the initial array and sparce table in order to compate subarrays fast and in order to find the first position of difference of subarrays that start at some positions $$$i$$$ and $$$j$$$.
Now let's consider all prefixes of the initial array in the order of increasing of length. We want to understand how does the suffix array of the current array changes when we add the integer to the right end of it. There are some prefix-independent subarrays (that is, subarrays that have the integer that differs them already added), and some segments of prefix-dependent subarrays. It is easy to see that the prefix-independent subarrays won't change their relative order. But prefix-depenent subarrays in one segment can change their relative order.
Suppose that you have the sorted sequence of pairwise different arrays $$$s_1, s_2, \ldots, s_n$$$ and each of them is the prefix of the next one. Then appending some integer $$$c$$$ to each of them and sorting them again are equivalent to the following operations:
• Let's split the sequence of arrays into two subsequences $$$s_{k_1}, s_{k_2}, \ldots, s_{k_x}$$$ and $$$s_{m_1}, s_{m_2}, \ldots, s_{m_y}$$$ in the following way: the first of them contains all such arrays $$$s_i$$$ that $$$i < n$$$ and $$$s_i + c \leq s_{i+1}$$$, the second of them contains all other arrays.
• The sorted sequence of arrays is equal to $$$s_{k_1} + c, s_{k_2} + c, \ldots, s_{k_x} + c, s_{m_y} + c, s_{m_{y-1}} + c, \ldots, s_{y_1} + c$$$. Prefix-dependent arrays can appear only in the first part of the sequence.
We can use sparce table to find the first position where prefix-dependent subarrays differ. Using the suffix array we can find the final order of these arrays.
Since we are interested only in the lexicographically smallest suffix we can maintain only some data about the first segment of prefix-dependent subarrays in the suffix array.
Let's call the suffix from the first segment such that its position in the final suffix array is the smallest important suffix. Then the suffixes that can be the lexicographically smallest now differs from the important suffix in come position later.
Let's maintain "the minimal suffix candidates" as a set of triples (the position of the beginning of this suffix, the position of this suffix in the final suffix array, the position where this suffix differs from the important suffix).
Here is the code that finds the minimal suffix of each prefix of the given array:
This part of the solution works in $$$\mathcal{O}(n \log^2 n)$$$ or in $$$\mathcal{O}(n \log n)$$$. It depends on your implementation of suffix array.
Part $$$3$$$.
For a given $$$r$$$ let the position of the beginning of the lexmin suffix of $$$c_1, c_2, \ldots, c_r$$$ be $$$l$$$.
For a subarray $$$c_l, \ldots, c_r$$$, I want to find the smallest $$$k$$$ such that $$$c_l, \ldots, c_r$$$ is a period of $$$c_k, \ldots, c_r$$$ (without a prefix).
It can be easily done by binary search or binary lifting in $$$\mathcal{O}(n \log n)$$$ for all $$$r$$$. We use the suffix array and sparce table from the previous part here.
Now, let's show that on the $$$(n-r+1)$$$-th step the lexicographically smallest subarray starts in one of positions $$$l$$$ and $$$k$$$ (for this $$$r$$$). Let $$$i = n - r + 1$$$.
Let's assume that the lexmin subarray starts in the position $$$x$$$ and $$$x \neq l$$$.
• If $$$c_l, \ldots, c_r$$$ is not a prefix of $$$c_x, \ldots, c_r$$$ then the subarray that starts at the position $$$l$$$ is not larger than the subarray that starts at the position $$$x$$$ according to the choice of $$$l$$$.
• By the same reasons $$$x < l$$$.
• Now we know that $$$c_l, \ldots, c_r$$$ is a prefix of $$$c_x, \ldots, c_r$$$. Let $$$p$$$ be the smallest positive integer such that $$$c_{l+p} \neq c_{x+p}$$$. Since we assumed that the lexmin subarray starts at the position $$$x$$$ then $$$c_{l+p} > c_{x+p}$$$. The case $$$x + p > x + i - 1$$$ is not interesting because subarrays of length $$$i$$$ from positions $$$l$$$ and $$$x$$$ are equal in this case.
• If $$$l + p \leq r$$$ then $$$c_l, \ldots, c_r$$$ is not a prefix of $$$c_x, \ldots, c_r$$$.
• If $$$x + p \leq r$$$ then we are in the following situation:  On the first picture the subarray that starts in position $$$x$$$ is shown. On the second picture the subarray that starts in position $$$l$$$ is show.$$$S$$$, $$$T$$$ are subarrays ($$$T$$$ can be empty), $$$a$$$, $$$b$$$ are the integers on position $$$x+p$$$ and $$$l+p$$$.The blue line splits the array into the prefix of the length $$$r$$$ and the suffix of the length $$$n-r$$$. Then we can show that the subarray that starts in the position $$$x+(r-l)+1$$$ is lexicographically smaller than the subarray we selected on the previous step. But it can't be true.
• If $$$x + p > r$$$ we can't get such a simple contradiction. But in this case we know that there are some items that appear in both subarrays. I will show that $$$c_l, \ldots, c_r$$$ is a period (without a prefix) of $$$c_x, \ldots, c_r$$$. Consider arrays $$$c_x, \ldots, c_{x+p-1}$$$ and $$$c_l, \ldots, c_{l+p-1}$$$.  Let $$$S$$$ be the subarray $$$c_l, \ldots, c_r$$$ and $$$T$$$ be the subarray $$$c_{x+(r-l)+1}, \ldots, c_r$$$. Then from equalities $$$c_y = c_{y-(l-x)}$$$ for $$$x + (r-l) \leq y < l+p$$$ follows that $$$T$$$ is a period of the subarray $$$c_{r + 1}, \ldots, c_{l+p-1}$$$.It is easy to see that the length of $$$T$$$ in at least the length of $$$S$$$ and that $$$T$$$ is lexicographically larger than $$$S$$$ according to the choise of $$$l$$$. But if the prefix of $$$T$$$ of length $$$|S|$$$ is larger than $$$S$$$, then it is incorrect that we have select the subarray that starts with $$$T$$$ on the previous step. Thus $$$S$$$ is a prefix of $$$T$$$. By the same reasons we can show that concatenation of $$$\alpha \leq \lfloor\frac{|T|}{|S|}\rfloor$$$ copies of $$$S$$$ is a prefix $$$T$$$. At the same time $$$S$$$ is a suffix of $$$T$$$. Thus $$$S$$$ is a period of $$$T$$$. If $$$|T| \bmod |S| \neq 0$$$ then the suffix of $$$S$$$ of length $$$|T| \bmod |S|$$$ is lexicographically smaller than $$$S$$$ but is makes a contradiction with the choise of $$$l$$$. Thus $$$S$$$ is a period of $$$T$$$ (without a prefix).
• The last thing to show is that $$$x = k$$$. Otherwise, $$$x - (r-l+1) \geq k$$$. It is easy to show that the subarray that starts in the position $$$x-(r-l+1)$$$ is not larger than the subarray that starts in the position $$$x$$$. It follows from the selection of $$$p$$$: $$$c_{l+p}$$$ makes the first difference between $$$c_{r+1}, \ldots, c_{n}$$$ and infinite concatenation of subarrays $$$c_l, \ldots, c_r$$$.
Part $$$4$$$.
Now we know that we should compare two subarrays that start from some known positions on each step. Let's deal with copying the subarray to the suffix.
Let's split an array into two parts. The first of them will consist of the first $$$n-i+1$$$ elements on the $$$i$$$-th step. The second of them will be the subarray we found on the previous step.
Let's store the second part as a queue of subarrays of the initial subarray. If we copy some subarray that doesn't intersect with the suffix, we just put it in the beginning of the queue. Otherwise, we can put the suffix of the current prefix into this queue.
We can maintain this queue in the segment tree with hashes. To compare two subarrays we will use the binary search. Total time complexity of this part is $$$\mathcal{O}(n \log^2 n)$$$.
There will be $$$M = \mathcal{O}(n \log n \log \log n) \approx 10^7$$$ hash comparations in the whole solution. The model solution uses the module near $$$10^{36}$$$.
I guess that it is possible to create a faster solution or solution without hashes using some ideas from the part $$$3$$$.
Bonus: how can we build the test that will break the hash comparation? is it true that the length of the subarray "prefix of T" from the picture above is either really small ($$$0$$$ or $$$1$$$) or huge ($$$|T| - 1$$$ or $$$|T| - 2$$$)? it is easy to see where the increasing order of lengths of subarrays is used; but is it necessary that these lengths are $$$1, \ldots, n$$$ in parts $$$2$$$-$$$4$$$ (in other worlds, is it possible to solve the problem that requires to make the given steps of $$$op$$$)?