#include<bits/stdc++.h>

using namespace std;

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

long long binary_search0(long long b[],long long 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;    
}


long long binary_search1(long long b[],long long 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;
}

long long binary_search2(long long b[],long long 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++;
	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)<<" ";
		if(x==1) cout<<binary_search1(a,y)<<" ";
		if(x==2) cout<<binary_search2(a,y)<<" ";
	}
	
	return 0;
}