/*
#include <iostream>
#include <vector>
using namespace std;
//Cirul lui Eratostene are O(MAXVAL) complexitate
//si determina toate numerele prime pana in acea
// valoare
vector<int>folosit;
const int MAXVAL=1e8;
int main()
{   folosit.resize(MAXVAL,0);
folosit[1]=folosit[0]=1;
    for(int i=2;i<=MAXVAL;i++){
           if(folosit[i]==0){
            for(int j=i+i;j<=MAXVAL;j+=i){
                folosit[j]=1;
            }
           }

    }
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        if(folosit[i]==0){
            cout<<i<<" ";
        }
    }
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
vector<int>x,y;
//Cautare  binara are ca si complexitate O(logN)
int n;
int cautareBinara(int a){
int s=1;
int dr=n;
while(s<=dr){
    int mij=(s+dr)/2;
    if(x[mij]<a){
        s=mij+1;
    }else if(x[mij]>a){
        dr=mij-1;
    }else if(x[mij]==a){
    return 1;
    }

}
return 0;
}
int main(){
    cin>>n;
    x.resize(n+1);
    for(int i=1;i<=n;i++){
        cin>>x[i];
    }
    int m;
    cin>>m;
    y.resize(m+1);
    for(int i=1;i<=m;i++){
        cin>>y[i];
    }
     for(int i=1;i<=m;i++){
        cin>>y[i];
        cout<<cautareBinara(y[i])<<" ";
    }
}
*/
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
vector<int>v;
int n;
int cautBin0(int x){
    int raspuns=-1;
    int st=1;
    int dr=n;
    while(st<=dr){
        int mij=(dr+st)/2;
        if(v[mij]==x){
            raspuns=mij;
            st=mij+1;
        }else if(v[mij]<x){
            st=mij+1;
        }else{
            dr=mij-1;
        }

    }
    return raspuns;
}
int cautBin1(int x){
    int raspuns=-1;
    int st=1;
    int dr=n;
    while(st<=dr){
        int mij=(dr+st)/2;
        if(v[mij]<=x){
            raspuns=mij;
            st=mij+1;
        }else{
            dr=mij-1;
        }

    }
    return raspuns;
}
int cautBin2(int x){
    int raspuns=-1;
    int st=1;
    int dr=n;
    while(st<=dr){
        int mij=(dr+st)/2;
        if(v[mij]>=x){
            raspuns=mij;
            dr=mij-1;
        }else{
            st=mij+1;
        }

    }
    return raspuns;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    v.resize(n+1);
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    int m;
    cin>>m;
    int tip,x;
    while(m){
        cin>>tip>>x;
        if(tip==0){
            cout<<cautBin0(x)<<'\n';
        }else if(tip==1){
             cout<<cautBin1(x)<<'\n';
        }else{
            cout<<cautBin2(x)<<'\n';
        }
        m--;
    }
}