#include<fstream>
using namespace std;
int v[100001],N,M,q,x,i,p,u,m;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int main(){
    fin>>N;
    for(i=1;i<=N;i++){
        fin>>v[i];
    }
    fin>>M;
    for(i=1;i<=M;i++){
        fin>>q>>x;
        if(q==0){
            p=1;
            u=N;
            while(p<=u){
                m=(p+u)/2;
                if(v[m]<=x){
                    p=m+1;
                }
                else
                    u=m-1;
            }
            if(v[u]==x){
                fout<<u<<"\n";
            }
            else
                fout<<-1<<"\n";
        }
        else{
            if(q==1){
                p=1;
                u=N;
                while(p<=u){
                    m=(p+u)/2;
                    if(v[m]<=x){
                        p=m+1;
                    }
                    else
                        u=m-1;
                }
                    fout<<u<<"\n";
                }
            else{
                p=1;
                u=N;
                while(p<=u){
                    m=(p+u)/2;
                    if(v[m]>=x){
                        u=m-1;;
                    }
                    else
                        p=m+1;
                    }
                fout<<p<<"\n";
            }
        }
    }
    return 0;
}