arekTOChuj

#include <bits/stdc++.h>

using namespace std;

//DEBUG
#define DEBUG 0


int KMR[200 * 1000][20];
int n;
int maxKMR;

int lastKMRnmbr = 1;

pair < pair <int, int>, int> pary[200 * 1000];
int ilePar;

int results[100 * 1000];

int main()
{
    if(!DEBUG){ios_base::sync_with_stdio(false); cin.tie(0);}

    cin >> n;

    for(int i = 0; i < n;i++)
    {
        cin >> KMR[i][0];
        KMR[n + i][0] = KMR[i][0];
    }

    for(maxKMR = 0; (1 << maxKMR) <= n; maxKMR++); maxKMR--;

    for(int lvl = 1; lvl <= maxKMR; lvl++)
    {
        int len = (1 << lvl);

        ilePar = 0;
        for(int i = 0; i + len - 1 < 2 * n; i++)
            pary[ilePar++] = {{KMR[i][lvl - 1], KMR[i + len/2][lvl - 1]}, i};

        sort(pary, pary + ilePar);

        if(DEBUG){for(int p = 0; p < ilePar; p++)cout << "[(" << pary[p].first.first << ", " << pary[p].first.second << "), " << pary[p].second << "] ";cout << "\n\n";}

        lastKMRnmbr++;
        for(int p = 0; p  < ilePar; p++)
        {
            if(p != 0 && pary[p].first != pary[p - 1].first)
                lastKMRnmbr++;

            KMR[pary[p].second][lvl] = lastKMRnmbr;
        }
    }

    if(DEBUG)
    for(int lvl = 0; lvl <= maxKMR; lvl++)
    {
        for(int i = 0; i < 2 * n; i++)
            cout << KMR[i][lvl] << ' ';

        cout << '\n';
    }


    for(int i = 0; i < n; i++)
        results[i] = i;

    sort(results, results + n, [](const int &a, const int &b)->bool
         {
            return (KMR[a][maxKMR] < KMR[b][maxKMR]) || (KMR[a][maxKMR] == KMR[b][maxKMR] && KMR[a + n - (1<<maxKMR)][maxKMR] < KMR[b + n - (1<<maxKMR)][maxKMR]);
         });

    if(DEBUG)
    {
        cout << "\n\nRESULTS:\n";
        for(int i = 0; i < n; i++)
            cout << results[i] << '\n';
        cout << "\n\n";
    }

    int qNmbr; cin >> qNmbr;

    for(int q = 0; q < qNmbr; q++)
    {
        int x, y;
        cin >> x >> y; x--; y--;

        cout << KMR[results[y] + x][0] << '\n';
    }


    return 0;
}