#include <stdio.h>
#define MaxN 100000
int n,cod,m,x;
int v[MaxN];
#define v (v-1)

int caut_bin1(int x,int lo,int hi){
	int mid=lo+(hi-lo)/2;
	if (lo>=hi && v[lo]!=x) return -1;
	if (v[mid]==x) 
		return mid;
	else if (v[mid]>x)
		return caut_bin1(x,lo,mid-1);
	else if (v[mid]<x)
		return caut_bin1(x,mid+1,hi);
}

int caut_bin2(int x)   
{   
    int lo, hi, mid, last = 0;   
  
    for (lo = 1, hi = n; lo <= hi; )   
    {   
        mid = lo + (hi-lo) / 2;   
        if (v[mid] <= x) last = mid, lo = mid+1;   
        else hi = mid-1;   
    }   
    return last;   
}   
 
int caut_bin3(int x)   
{   
    int lo, hi, mid, last = n+1;   
  
    for (lo = 1, hi = n; lo <= hi; )   
    {   
        mid = lo + (hi-lo) / 2;   
        if (x <= v[mid]) last = mid, hi = mid-1;   
        else lo = mid+1;   
    }   
    return last;   
}   
int main(){
	freopen ("cautbin.in","r",stdin);
	freopen ("cautbin.out","w",stdout);

	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d",&v[i]);
	scanf("%d",&m);
	for (int i=1;i<=m;i++){
		scanf("%d",&cod);
		switch (cod){
			case 0 :
				scanf("%d",&x);
				printf ("%d \n",caut_bin1(x,1,n));
				break;
			case 1 :
				scanf("%d",&x);
				printf("%d \n",caut_bin2(x));
				break;
			case 2 :
				scanf("%d",&x);
				printf("%d \n",caut_bin3(x));
				break;
		}
	}
}