#include<bits/stdc++.h>

using namespace std;

int n,m,a[100001],i,x,y,lo,hi,mid;

int binary_search0(int b[],int target){
	lo=b[1];
	hi=b[n];
    while (lo<=hi){
        mid = lo + (hi-lo)/2;
        if (b[mid]<=target)
            lo=mid+1;
		else
			hi=mid-1;
	}
    mid = lo + (hi-lo)/2;
	if(b[mid]>target) mid--;
	if(b[mid]==target) return mid;
	  
    return -1;    
}


int binary_search1(int b[],int target){
	lo=b[1];
	hi=b[n];
    while (lo<hi){
        mid = lo + (hi-lo)/2;
        if (b[mid]<=target)
            lo=mid+1;
		else
			hi=mid;
	}
    mid = lo + (hi-lo)/2;
	if(b[mid]>target) mid--;
	return mid;
}

int binary_search2(int b[],int target){
    lo=b[1];
	hi=b[n];
    while (lo<hi){
        mid = lo + (hi-lo)/2;
        if (b[mid]<target)
            lo=mid+1;
		else
			hi=mid;
	}
    mid = lo + (hi-lo)/2;
	if(b[mid]<target) mid++;
	return mid;
}


int main(){
	ifstream cin("cautbin.in");
	ofstream cout("cautbin.out");
	cin>>n;
	for( i=1; i<=n; i++)
		cin>>a[i];
	cin>>m;
	for( i=1; i<=m; i++){
		cin>>x;
		cin>>y;
		if(x==0) cout<<binary_search0(a,y)<<endl;
		if(x==1) cout<<binary_search1(a,y)<<endl;
		if(x==2) cout<<binary_search2(a,y)<<endl;
	}
	
	return 0;
}