Задача . I. Две последовательности

Рассмотрим некоторый массив целых чисел \(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\).