#include<iostream>
#include<fstream>
using namespace std;
int v[100001],n,m;
int bsearch0(int l,int r,int key){
	int mid;
	while(l<=r){
		mid=(l+r)/2;
		if(v[mid]<=key)
			l=mid+1;
		else
			r=mid-1;
	}
	mid=(l+r)/2;
	if(v[mid]>key)
		mid--;
	if(v[mid]==key)return mid;
	return -1;
}
int bsearch1(int l,int r,int key){
	int mid;n=r;
	while(l<r){
		mid=(l+r)/2;
		if(v[mid]<=key)
			l=mid+1;
		else
			r=mid;
	}
	mid=(l+r)/2;
	if(v[mid]>key)
		--mid;
	return mid;
}

int bsearch2(int l,int r,int key){
	int mid;
	while(l<r){
		mid=(l+r)/2;
		if(v[mid]<key)
			l=mid+1;
		else
			r=mid;
	}
	mid=(l+r)/2;
	if(v[mid]<key)
		++mid;
	return mid;
}
int main(){
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	f>>n;
	for(int i=1;i<=n;i++)
		f>>v[i];
	f>>m;
	for(int i=1;i<=m;i++){
		int op,key;
		f>>op>>key;
		if(op==0)g<<bsearch0(1,n,key)<<endl;
		if(op==1)g<<bsearch1(1,n,key)<<endl;
		if(op==2)g<<bsearch2(1,n,key)<<endl;
	}
	f.close();
	g.close();
	return 0;
}