Oh no, sorting#12371
Scientists have invented a new type of sorting. Let's call the projector sorting of an array of length the following procedure:
the array is divided into consecutive subsegments of lengths 1, 2, 3, \dots;
if there are not enough elements for the next subsegment, it consists of all remaining elements;
each of these subsegments is independently sorted in non-decreasing order;
after that, the subsegments are written in the same order.
For example, the array [5, 4, 3, 2, 1, 0] is divided into subsegments , , [2, 1, 0]. After sorting, we get the array [5, 3, 4, 0, 1, 2]. The array [8, 5, 4, 7, 1] is divided into consecutive subsegments , , . The last subsegment is incomplete since its length is instead of . After sorting each subsegment separately, we get the array [8, 4, 5, 1, 7].
You are given an array of length and queries of the form [l, r, k].
For each query, consider the array obtained from after applying projector sorting to the subsegment . All elements outside this subsegment remain unchanged.
For each query, you need to find the of the subsegment in the resulting array.
Recall that the of an array is the smallest non-negative integer that does not appear among its elements.
For example, the of the array [0, 1, 2, 4, 5] is , since the number is the smallest non-negative integer that does not appear in the array.
The first line contains one integer (1 \le n \le 2 \cdot 10^5) — the length of the array .
The second line contains integers, a_1, a_2, ..., a_n (0 \le a_i \le 10^6) — the array .
The third line contains one integer (1 \le q \le 2 \cdot 10^5) — the number of queries.
In the next lines, there are three integers l, r, k (1 \le l \le r \le n, l \le k \le r) — the queries.
For each query, output one integer — the of the subsegment after applying projector sorting to the subsegment .
Example 1
For the first query, the array will look like , so the answer is .
For the second query, the array will look like [1,0,2], so for the segment , the answer is .
For the third query, the array will look like [1,0,2], so for the segment , the answer is .
For the fourth query, the array will look like [1,0,2,1,3,17,0], so for the segment , the answer is .
For the fifth query, the array will look like [1,0,2,1,3,17,0], so for the segment , the answer is .
For the sixth query, the array will look like [1,0,2,1,3,17,0], so for the segment , the answer is .
Subtask ( points) : (n \le 10)
Subtask ( points) : (l = 1)
Subtask ( points) : (q = 1)
Subtask ( points) : (n , q \le 2000)
Subtask ( points) : (a_i \le 10)
Subtask ( points) : (r-l+1 = \frac{m \cdot (m+1)}{2} , for some integer
Subtask ( points) : Without additional constraints