#include<fstream>
using namespace std;
int v[100001],N,M,a,b,i;
int cautbin0(int x,int p,int u){
            int m;
            while(p<=u){
                m=(p+u)/2;
                if(v[m]<=x){
                    p=m+1;
                }
                else
                    u=m-1;
            }
            if(v[u]==x){
                return u;
            }
            else
                return -1;
}
int cautbin1(int x,int p,int u){
            int m;
            while(p<=u){
                m=(p+u)/2;
                if(v[m]<=x){
                    p=m+1;
                }
                else
                    u=m-1;
            }
            if(v[u]<=x){
                return u;
            }
}
int cautbin2(int x,int p,int u){
            int m;
            while(p<=u){
                m=(p+u)/2;
                if(v[m]>=x){
                    u=m-1;;
                }
                else
                    p=p+1;
            }
            if(v[p]>=x){
                return p;
            }
}

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>>a>>b;
        if(a==0){
            fout<<cautbin0(b,1,N)<<"\n";
        }
        else{
            if(a==1){
                fout<<cautbin1(b,1,N)<<"\n";
            }
            else
                fout<<cautbin2(b,1,N)<<"\n";
        }
    }
    return 0;
}