#include <fstream>

using namespace std;

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

const int nmax=100000;
int v[nmax+1];

int main () {
    int n, m;
    fin>>n;
    int n2;
    for ( n2 = 1; n2 <= n; n2 *= 2 ) {
    }
    n2 /= 2;

    for (int i=1; i<=n; i++) {
        fin>>v[i];
    }

    fin>>m;
    for  (int i=1; i<=m; i++) {
        int x,y;
        fin>>x>>y;
        if (x==0) {
            int sol = 0;
            for ( int step = n2; step > 0; step /= 2 ) {
                if ( sol+step <= n && v[sol+step] <= y ) {
                    sol += step;
                }
            }
            if ( v[sol] != y ) {
                sol = -1;
            }
            fout << sol << "\n";
        } else if(x==1) {
            int sol=0;
            for (int step=n2; step>0; step/=2) {
                if (sol+step<=n && v[sol+step]<=y) {
                    sol=sol+step;
                }
            }
            fout<<sol<<"\n";
        }else {
            int sol=n+1;
            for (int step=n2; step>0; step/=2) {
                if (sol-step>=1 && v[sol-step]>=y) {
                    sol=sol-step;
                }
            }
            fout<<sol<<"\n";
        }
    }

    return 0;
}