#include<cstdio>
using namespace std;
int a[100001],n;

int query1(int x){
	int l=1,r=n,mid;

	while(l!=r){
		mid=l+(r-l)/2;
		if(x>=a[mid]){
			l=mid+1;
			continue;
		}
		else{
			r=mid-1;
		}
	}
	mid=l+(r-l)/2;
	if(a[mid]>x) --mid;
	if(a[mid]==x) return mid; 
	return -1;
}

int query2(int x){
	int l=1,r=n,mid;

	while(l<r){
		mid=l+(r-l)/2;
		if(x>=a[mid]){
			l=mid+1;
			continue;
		}
		else{
			r=mid-1;
		}
	}
	if(a[mid]>x) --mid;
	return mid;
}

int query3(int x){
	 int mid,l=1,r=n;
 	
    while (l < r) {
        mid = (l + r) / 2;
        if (a[mid] < x)
            l = mid + 1;
        else
            r = mid;
    }
     
    mid = (l + r) / 2;
    if (a[mid] < x)
       ++ mid;
    return mid;
}


int main(){
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",a+i);
	int m; scanf("%d",&m);
	int cod,x,q;
	while(m>0){
		--m;
		scanf("%d%d",&cod,&x);
		switch(cod){
			case 0:{
				q=query1(x);
				break;
			}
			case 1:{
				q=query2(x);
				break;
			}
			case 2:{
				q=query3(x);
			}
		}
	printf("%d\n",q);
	}

	return 0;
}