#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int v[100005];

int BinSearch1(int st, int dr, int val){
    int ans=0;
    while(st<=dr){
        int med=(st+dr)/2;
        if(v[med]<=val){
            st=med+1;
            ans=med;
        }else{
            dr=med-1;
        }
    }
    return ans;
}
int BinSearch2(int st, int dr, int val){
    int ans=0;
    while(st<=dr){
        int med=(st+dr)/2;
        if(v[med]>=val){
            dr=med-1;
            ans=med;
        }else{
            st=med+1;
        }
    }
    return ans;
}

int main()
{   int n;
    fin>>n;
    for(int i=1; i<=n; i++){
        fin>>v[i];
    }
    int m;
    fin>>m;
    for(int k=1; k<=m; k++){
        int op, nr;
        fin>>op>>nr;
        if(op==0){
            int ras;
            ras=BinSearch1(1, n, nr);
            if(v[ras]==nr){
                fout<<ras<<"\n";
            }else{
                fout<<"-1"<<"\n";
            }
        }else if(op==1){
            fout<<BinSearch1(1, n, nr)<<"\n";
        }else if(op==2){
            fout<<BinSearch2(1, n, nr)<<"\n";
        }
    }

    return 0;
}