#include <fstream>

using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");

const int L=16;
const int N = 100001;

int v[N];
int n;

int caut0 (int x){
    int r = 0;
    int pas = 1<<L;
	while(pas!=0){
        if(r+pas<=n && v[r+pas]<= x){
            r+=pas;
        }
        pas/=2;
	}
	if(v[r]<x){
        r=-1;
	}
	return r;

}

int caut1 (int x){
	int r = 0;
	int pas = 1<<L;
	while(pas!=0){
        if(r+pas<=n && v[r+pas]<= x){
            r+=pas;
        }
        pas/=2;
	}
	return r;
}

int caut2(int x){
	int r = 0;
	int pas = 1<<L;
	while(pas!=0){
        if(r+pas<=n && v[r+pas]< x){
            r+=pas;
        }
        pas/=2;
    }
    r++;
    return r;
}



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

}