#include<fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int n,m,v[100000],ok,st,dr,mid,i,k,t,x;
int main(){
    in >> n;
    for( i = 1; i <= n; i ++ ){
        in  >> v[i];
    }
    in >> k;
    for( i = 1; i <= k; i ++ ){
        in >> t >> x;
        st=1;
        dr=n;
        ok=-1;
        if(t==0){

        while(st<=dr){
            mid=(dr+st)/2;
            if(v[mid]<=x){
                st=mid+1;
            }
            if(v[mid]>x){
                dr=mid-1;
            }
            if(v[mid]==x){
                ok=1;
            }


        }
                if(ok==1){
                out<<dr<<"\n";}
                else
                    out<<ok<<"\n";
        }
        if(t==1){
        while(st<=dr){
            mid=(dr+st)/2;
            if(v[mid]<=x){
                st=mid+1;
            }
            if(v[mid]>x){
                dr=mid-1;
            }


        }
            out<<dr<<"\n";

         }
        if(t==2){
        while(st<=dr){
            mid=(dr+st)/2;
            if(v[mid]<x){
                st=mid+1;
            }
            if(v[mid]>=x){
                dr=mid-1;
            }


        }
            out<<st<<"\n";
        }

    }






return 0;
}