#include <fstream>

using namespace std;

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

const int nmax= 100000;

int n, m;
int v[nmax+1];

int n2;

int bsi(int x)
{
    int i, step= n2;

    for ( i= 1; step; step>>=1 ) {
        if ( i+step<=n && v[i+step]<=x ) {
            i+=step;
        }
    }

    return i;
}

int bsd(int x)
{
    int i, step= n2;

    for ( i= n; step; step>>=1 ) {
        if ( i-step>0 && v[i-step]>=x ) {
            i-=step;
        }
    }

    return i;
}

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

    for ( n2= 1; n2<n; n2<<=1 );

    fin>>m;
    for ( int i= 1; i<=m; ++i ) {
        int c, x, sol;
        fin>>c>>x;
        if ( c==0 ) {
            c= bsi(x);
            if ( v[c]!= x) {
                sol=-1;
            } else {
                sol=c;
            }
        } else if ( c==1 ) {
            sol =bsi(x);
        } else {
            sol =bsd(x);
        }

        fout<<sol<<"\n";
    }

    return 0;
}