#include <fstream>

using namespace std;

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

const int nmax= 100000;
const int pmax= 65536;

int v[nmax+1];

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

    fin>>m;
    for ( int i= 0, x, y, sol; i<m; ++i ) {
        fin>>x>>y;

        if ( x<=1 ) {
            sol= 0;
            for ( int step= pmax; step>0; step/= 2 ) {
                if ( sol+step<=n && v[sol+step]<=y ) {
                    sol+= step;
                }
            }

            if ( x==0 && v[sol]!=y ) {
                sol= -1;
            }
        } else {
            sol= n;
            for ( int step= pmax; step>0; step/= 2 ) {
                if ( sol-step>=1 && v[sol-step]>=y ) {
                    sol-= step;
                }
            }
        }

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

    return 0;
}