CF1621I 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 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 $ .

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] $ .