A14844. Two Sequences
编程题
普及/提高-
知识点
题目描述
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$ .
- 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$ .
输入格式
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.
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$ .
输入输出样例
输入 #1
4 2 1 3 1 4 1 1 1 2 1 3 1 4
输出 #1
2 1 1 3
说明/提示
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]$ .
$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]$ .