#include <fstream>
#define N 100005

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n, m, a[N], poz;

int CautareBinara(int operatie, int nr) {

    int st = 1, dr = n, mij;

    if (operatie == 0) {

        while(st <= dr) {

            mij = st + (dr - st) / 2;
            if(a[mij] == nr && a[mij + 1] != nr) { return mij; }
            else if(a[mij] == nr && a[mij + 1] == nr) { st = mij + 1; }
            else if(a[mij] < nr) { st = mij + 1; }
            else if(a[mij] > nr) { dr = mij - 1; }
          }

        return -1;
    }

    else if (operatie == 1) {

        while(st <= dr) {

            mij = st + (dr - st) / 2;
            if(a[mij] == nr && a[mij + 1] != nr) { return mij; }
            else if(a[mij] == nr && a[mij + 1] == nr) { st = mij + 1; }
            else if(a[mij] < nr) { st = mij + 1; }
            else if(a[mij] > nr) { dr = mij - 1; }
          }

        if(a[mij] < nr) return mij;
        if(a[mij] > nr) return mij-1;
    }

   else if (operatie == 2) {

        while(st <= dr) {

            mij = st + (dr - st) / 2;
            if(a[mij] == nr && a[mij - 1] != nr) { return mij; }
            else if(a[mij] == nr && a[mij - 1] == nr) { dr = mij - 1; }
            else if(a[mij] < nr) { st = mij + 1; }
            else if(a[mij] > nr) { dr = mij - 1; }
          }

        if(a[mij] < nr) return mij + 1;
        if(a[mij] > nr) return mij;
    }
}

int main()
{
    int i, x, op, numar;

    fin >> n;

    for ( i = 1; i <= n; i++ )
        fin >> a[i];

    fin >> m;

    for ( i = 1; i <= m; i++ ) {

        fin >> op >> numar;
        poz = CautareBinara(op, numar);

        fout << poz << "\n";
    }

    return 0;
}