#include <bits/stdc++.h>


using namespace std;


#define nmax 100014


int vect[nmax],n,x,m,i,tip,rezultat;


int cautarebinaraMare(){
    int st=1,dr=n,mijloc;
    while(st<=dr){
        mijloc=(st+dr)/2;
        if(vect[mijloc]<=x)
            st=mijloc+1;
        else
            dr=mijloc- 1;
    }
    return dr;
}


int cautarebinaraMica(){
    int st = 1, dr = n, mijloc;
    while(st<=dr){
        mijloc=(st+dr)/2;
        if(vect[mijloc]<x)
            st=mijloc+1;
        else
            dr=mijloc-1;
    }
    return st;
}


int main()
{


    int i,tip,rezultat;
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>vect[i];
    fin>>m;
    for(i=1;i<=m;i++){
        fin>>tip>>x;
        if(tip==0){
            rezultat=cautarebinaraMare();
            if(vect[rezultat]!=x)
                rezultat=-1;
        }
        if(tip==1)
            rezultat=cautarebinaraMare();
        else if(tip==2){
            rezultat=cautarebinaraMica();
        }
        fout<<rezultat<<'\n';
    }
    return 0;
}