#include <stdio.h>
#define N 100000


int vec[N];

int search_1 (int n , int m , int k){
int mid;

	while (n <= m) {
		mid=(n+m)/2;
		if (vec[mid] <= k) 
			n=mid+1;
		else	
			m=mid-1;
		}
	mid=(m+n)/2;
	if (vec[mid] > k) 	
		mid--;
	if (vec[mid] == k)
		return mid;
return -1;
}
			
int search_2 (int n, int m, int k){
int mid;
	
	while(n<m) {
		mid=(m+n)/2;
		if (vec[mid] <=k)
			n=mid+1;
		else 
			m=mid;
	}
	mid=(m+n)/2;
	if (vec[mid]>k)
		mid--;
	return mid;
}

int search_3(int n, int m, int k){
int mid;

	while (n<m) {
		mid=(m+n)/2;
		if (vec[mid]<k)
			n=mid+1;
		else 
			m=mid;
	}
	mid=(m+n)/2;
	if (vec[mid]<k)
		mid++;
	return mid;
}


int main () {
    int i, n, m, tip, val;

    FILE *in=fopen("cautbin.in","r");
    FILE *out=fopen("cautbin.out","w");
    fscanf(in,"%d", &n);
    for (i = 1; i <= n; ++ i)
        fscanf(in,"%d", &vec[i]);
    
    fscanf(in,"%d", &m);

    while (m --){
          fscanf(in,"%d%d", &tip, &val);
          if (tip == 0)
             fprintf(out,"%d\n", search_1(1, n, val));
          if (tip == 1)
             fprintf(out,"%d\n", search_2(1, n, val));
          if (tip == 2)
             fprintf(out,"%d\n", search_3(1, n, val));
    }
    fclose(in);
    fclose(out);
return 0;
}