I. Две последовательности
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим некоторый массив целых чисел $$$C = [c_1, c_2, \ldots, c_n]$$$ длины $$$n$$$. Построим последовательность массивов $$$D_0, D_1, D_2, \ldots, D_{n}$$$ длины $$$n+1$$$ следующим образом:

  • Первый массив в этой последовательности будет равен $$$C$$$: $$$D_0 = C$$$.
  • Для всех $$$1 \leq i \leq n$$$ массив $$$D_i$$$ будет получен из $$$D_{i-1}$$$ следующим образом:
    • Рассмотрим лексикографически наименьший подмассив $$$D_{i-1}$$$ длины $$$i$$$. Тогда первые $$$n-i$$$ элемент массива $$$D_i$$$ будут равны первым $$$n-i$$$ элементам массива $$$D_{i-1}$$$ соответственно, а последние $$$i$$$ элементов массива $$$D_i$$$ будут равны соответствующим элементам этого подмассива длины $$$i$$$.

Массив $$$x$$$ является подмассивом массива $$$y$$$, если $$$x$$$ может быть получен удалением нескольких (возможно, ни одного или всех) элементов из начала $$$y$$$ и нескольких (возможно, ни одного или всех) элементов из конца $$$y$$$.

Для массива $$$C$$$ обозначим массив $$$D_n$$$ как $$$op(C)$$$.

У Алисы есть массив целых чисел $$$A = [a_1, a_2, \ldots, a_n]$$$ длины $$$n$$$. Она построит последовательность массивов $$$B_0, B_1, \ldots, B_n$$$ длины $$$n+1$$$ следующим образом:

  • Первый массив в этой последовательности будет равен $$$A$$$: $$$B_0 = A$$$.
  • Для всех $$$1 \leq i \leq n$$$ массив $$$B_i$$$ будет равен $$$op(B_{i-1})$$$, где $$$op$$$ — преобразование, определённое выше.

Алиса задаст Вам $$$q$$$ запросов про элементы последовательности массивов $$$B_0, B_1, \ldots, B_n$$$. Запрос состоит из двух чисел $$$i$$$ и $$$j$$$, а ответом на него будет значение $$$j$$$-го элемента массива $$$B_i$$$.

Входные данные

В первой строке дано одно число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — длина массива $$$A$$$.

Во второй строке дано $$$n$$$ чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — массив $$$A$$$.

В третьей строке дано одно число $$$q$$$ ($$$1 \leq q \leq 10^6$$$) — количество запросов.

Следующие $$$q$$$ строк содержат по два числа $$$i$$$, $$$j$$$ ($$$1 \leq i, j \leq n$$$) — параметры запросов.

Выходные данные

Выведите $$$q$$$ целых чисел: значения $$$B_{i, j}$$$ для требуемых $$$i$$$, $$$j$$$.

Пример
Входные данные
4
2 1 3 1
4
1 1
1 2
1 3
1 4
Выходные данные
2
1
1
3
Примечание

В первом тесте $$$B_0 = A = [2, 1, 3, 1]$$$.

$$$B_1$$$ вычисляется следующим образом:

  • Изначально, $$$D_0 = [2, 1, 3, 1]$$$.
  • Для $$$i=1$$$ лексикографически минимальным подмассивом $$$D_0$$$ длины $$$1$$$ является $$$[1]$$$, $$$D_1$$$ будет равен $$$[2, 1, 3, 1]$$$.
  • Для $$$i=2$$$ лексикографически минимальным подмассивом $$$D_1$$$ длины $$$2$$$ является $$$[1, 3]$$$, $$$D_2$$$ будет равен $$$[2, 1, 1, 3]$$$.
  • Для $$$i=3$$$ лексикографически минимальным подмассивом $$$D_2$$$ длины $$$3$$$ является $$$[1, 1, 3]$$$, $$$D_3$$$ будет равен $$$[2, 1, 1, 3]$$$.
  • Для $$$i=4$$$ лексикографически минимальным подмассивом $$$D_3$$$ длины $$$4$$$ является $$$[2, 1, 1, 3]$$$, $$$D_4$$$ будет равен $$$[2, 1, 1, 3]$$$.
  • Таким образом, $$$B_1 = op(B_0) = op([2, 1, 3, 1]) = [2, 1, 1, 3]$$$.