Hello 2022 |
---|
Finished |
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:
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:
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$$$.
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 $$$q$$$ integers: values of $$$B_{i, j}$$$ for required $$$i$$$, $$$j$$$.
4 2 1 3 1 4 1 1 1 2 1 3 1 4
2 1 1 3
In the first test case $$$B_0 = A = [2, 1, 3, 1]$$$.
$$$B_1$$$ is constructed in the following way:
Name |
---|