Strange Permutation
Contest: Codeforces Round 694 (Div. 1)
Difficulty rating: 3200
Tags: binary search, combinatorics, data structures, dp, graphs, implementation, two pointers

Alice had a permutation $$$p_1, p_2, \ldots, p_n$$$. Unfortunately, the permutation looked very boring, so she decided to change it and choose some non-overlapping subranges of this permutation and reverse them. The cost of reversing a single subrange $$$[l, r]$$$ (elements from position $$$l$$$ to position $$$r$$$, inclusive) is equal to $$$r - l$$$, and the cost of the operation is the sum of costs of reversing individual subranges. Alice had an integer $$$c$$$ in mind, so she only considered operations that cost no more than $$$c$$$.

Then she got really bored, and decided to write down all the permutations that she could possibly obtain by performing exactly one operation on the initial permutation. Of course, Alice is very smart, so she wrote down each obtainable permutation exactly once (no matter in how many ways it can be obtained), and of course the list was sorted lexicographically.

Now Bob would like to ask Alice some questions about her list. Each question is in the following form: what is the $$$i$$$-th number in the $$$j$$$-th permutation that Alice wrote down? Since Alice is too bored to answer these questions, she asked you to help her out.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 30$$$) — the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$c$$$, $$$q$$$ ($$$1 \leq n \leq 3 \cdot 10^4$$$, $$$1 \leq c \leq 4$$$, $$$1 \leq q \leq 3 \cdot 10^5$$$) — the length of the permutation, the maximum cost of the operation, and the number of queries.

The next line of each test case contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \leq p_i \leq n$$$, $$$p_i \neq p_j$$$ if $$$i \neq j$$$), describing the initial permutation.

The following $$$q$$$ lines describe the queries. Each of them contains two integers $$$i$$$ and $$$j$$$ ($$$1 \leq i \leq n$$$, $$$1 \leq j \leq 10^{18}$$$), denoting parameters of this query.

It is guaranteed that the sum of values $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$, and the sum of values $$$q$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output format:
For each query output the answer for this query, or $$$-1$$$ if $$$j$$$-th permutation does not exist in her list.

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

Note:
In the first test case, Alice wrote down the following permutations: $$$[1, 2, 3]$$$, $$$[1, 3, 2]$$$, $$$[2, 1, 3]$$$.

Note that, for a permutation $$$[3, 2, 1]$$$ Alice would have to reverse the whole array, and it would cost her $$$2$$$, which is greater than the specified value $$$c=1$$$. The other two permutations can not be obtained by performing exactly one operation described in the problem statement.

Example input:
2
3 1 9
1 2 3
1 1
2 1
3 1
1 2
2 2
3 2
1 3
2 3
3 3
6 4 4
6 5 4 3 1 2
1 1
3 14
1 59
2 6

Example output:
1
2
3
1
3
2
2
1
3
1
4
-1
5

Example input:
1
12 4 2
1 2 3 4 5 6 7 8 9 10 11 12
2 20
2 21

Example output:
2
2

Editorial:
Let call the cost of rotation of segment $$$[L, R]$$$ value $$$R - L$$$ coins.
Let's calculate how many ways can we apply to the array of length $$$len$$$ with total cost less or equal to $$$c$$$. We can fix $$$len - 1$$$ bars between neighbouring elements of array. There is a bijection between ways to select $$$c$$$ of them and ways to apply some not overlapping rotations with total cost equals $$$c$$$. We can see, that the number of ways is equals $$${{len-1}\choose{0}} + \dots + {{len-1}\choose{c}} = ways(len, c)$$$. Now we can check if the answer to the query is $$$-1$$$.
It is easy to see, that the answer on query depends only on construction of $$$j$$$-th permutation from $$$p$$$. This construction can be represented as set of rotations of size not larger than $$$c$$$. And the number of possible rotations in this set doesn't exceed $$$m = nc$$$. If we can answer this query for each suffix of $$$p$$$, we can determine $$$j$$$-th permutation:
• $$$l$$$ $$$c$$$ $$$k$$$ What is the leftmost rotation on the suffix of length $$$len$$$, if we have $$$c$$$ coins and we want to get $$$k$$$-th permutation of this suffix.
Let's fix any suffix $$$p_x, p_{x+1}, \dots, p_n$$$. We can build a long array consisting of the leftmost rotations in construction of each permutation of this suffix using not more than $$$c$$$ coins. It is easy to see that each rotation will appear on some segment of this array. We can determine the length of this segment: if it was the rotation $$$[l, r]$$$, than the length of this segment is $$$ways(n - r, c - r + l)$$$. Exactly once happends that there is no leftmost rotation.
For $$$x-1$$$ (suffix $$$p_{x-1}, p_x, \dots, p_n$$$) relative order of this segments won't change because we will add $$$p_{x-1}$$$ to the beginning of each permutation. Only $$$c$$$ segments will appear (rotations $$$[x-1, x], [x-1, x+1], \dots, [x-1, x+c-1]$$$).
We can show that new segment will appear only in the beginning and in the end (because only their first element isn't equal $$$p_{x-1}$$$).
We can show that query $$$l$$$ $$$c$$$ $$$k$$$ is equivalent to query $$$n$$$ $$$c$$$ $$$k'$$$ because of the structure of this array.
In $$$\mathcal{O}(m)$$$ we can build this array using deque. We should do this for each $$$c$$$.
Let's answer the queries offline using the following algorithm:
• Iterate in order of decreasing $$$c$$$ (let's call a level set of queries with the same $$$c$$$).
• Sort queries in order of increasing $$$k$$$. Using two pointers approach we can move all queries to another level and change them to type $$$n$$$ $$$c$$$ $$$k'$$$.
If we will remove queries from each level after answering them, memory will be reduced from $$$\mathcal{O}(qc + nc)$$$ to $$$\mathcal{O}(q + nc)$$$.
Total work time: $$$\mathcal{O}(sort(q) \cdot c + nc^2)$$$. It can be optimized to $$$\mathcal{O}(sort(q) + q \cdot log{n} \cdot log{c} + nc^2)$$$ using another sort algorithms. Also there is a solution in $$$\mathcal{O}(nc^2 + q \cdot c \cdot log(nc))$$$ and $$$\mathcal{O}(nc)$$$ memory with binary search and slower solutions with different data structures.