#include <bits/stdc++.h>

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

int binary_search1(int v[],int n,int x){
    int st=upper_bound(v,v+n,x)-v;
    if(v[st-1]==x){
        return st;
    }
    return -1;
}
int binary_search2(int v[],int n,int x){
    return upper_bound(v,v+n,x)-v;
}
int binary_search3(int v[],int n,int x){
    return lower_bound(v,v+n,x)-v+1;
}

int main()
{
    int v[100000],n,m,q,x;
    in>>n;
    for(int i=0;i<n;i++){
        in>>v[i];
    }
    in>>m;
    for(int i=0;i<m;i++){
        in>>q>>x;
        if(q==0){
            out<<binary_search1(v,n,x)<<"\n";
        }else if(q==1){
            out<<binary_search2(v,n,x)<<"\n";
        }else{
            out<<binary_search3(v,n,x)<<"\n";
        }
    }
    return 0;
}