#include <fstream>
using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int x[25001], n, i, m, med, st, dr, ans, t, r;
int cautare1(int t){
    st=1;
    dr=n;
    while(st<=dr){
        med=(st+dr)/2;
        if(x[med]<=t){
            st=med+1;
            ans=med;
        } else {
            dr=med-1;
        }
    }
    return ans;
}
int cautare2(int t){
    st=1;
    dr=n;
    while(st<=dr){
        med=(st+dr)/2;
        if(x[med]>=t){
            dr=med-1;
            ans=med;
        } else {
            st=med+1;
        }
    }
    return ans;
}

int main(){
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>x[i];
    }
    cin>>m;
    for(i=1;i<=m;i++){
        cin>>r>>t;
        if(r==0){
            if(x[cautare1(t)]==t){
                cout<<cautare1(t)<<endl;
            } else {
                cout<<-1<<endl;
            }
        } else if(r==1){
            cout<<cautare1(t)<<endl;
        } else if(r==2){
            cout<<cautare2(t)<<endl;
        }
    }
    return 0;
}