#include<bits/stdc++.h>

using namespace std;
int lo,hi,mid,a[101001],x,n,t,y;

int cautbin0(){
	lo=1;
	hi=n;
	while(lo<=hi){
		mid=lo+(hi-lo)/2;
		//if(x==a[mid]) break;
		if(x>=a[mid]) lo=mid+1;
		if(x<a[mid]) hi=mid-1;
	}
	mid=lo+(hi-lo)/2;
	if(a[mid]>x) mid--;
	if(a[mid]==x) return mid;
	return -1;
}
int cautbin1_versiunea_lui_SuperGheoghe(){
	lo=1;
	hi=n;
	while(lo<=hi){
		mid=lo+(hi-lo)/2;
		if(a[mid]>x) hi=mid-1;
		else lo=mid+1;
	}
	mid=lo+(hi-lo)/2;
	if(a[mid]<=x) return mid;
	else if(a[mid-1]<=x) return mid-1;
	//if(a[mid]==x) return mid;
	return -1;
}
int cautbin2(){
	lo=1;
	hi=n;
	while(lo<=hi){
		mid=lo+(hi-lo)/2;
		if(a[mid]>=x) hi=mid-1;
		else lo=mid+1;
	}
	mid=lo+(hi-lo)/2;
	if(a[mid]>=x) return mid;
	else if(a[mid+1]>=x) return mid;
	return -1;
}

int main(){
	ifstream cin("cautbin.in");
	ofstream cout("cautbin.out");
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	cin>>t;
	for(int i=1;i<=t;i++){
		cin>>y>>x;
		if(y==0) cout<<cautbin0()<<endl;
		if(y==1) cout<<cautbin1_versiunea_lui_SuperGheoghe()<<endl;
		if(y==2) cout<<cautbin2();
	}
	return 0;
}