#include <stdio.h>
#include <stdlib.h>    

int cautbin1(int x, int v[])
{
	int low, high, mid, sol = -1;
	low = 1;
	high = v[0];
	while (low < high)
	{
		mid = low + (high - low)/2;
		if (x > v[mid])
			low = mid + 1;
		if (x < v[mid])
			high = mid - 1;
		if (x == v[mid]) {
			sol = mid;
			low = mid + 1;
		}
	}
	return sol;
}

int cautbin2(int x, int v[])
{       
	int low, high, mid, sol = -1;
	low = 1;
	high = v[0];
	while (low < high)
	{
		mid = low + (high - low)/2;
		if (x >= v[mid]) {
			low = mid + 1;
			sol = mid;
		}
		if (x < v[mid]) {
			high = mid - 1;
		}
	}
	if (v[low] <= x)
		sol = low;
	return sol;  
}

int cautbin3(int x, int v[])
{
	int low, high, mid, sol = -1;
	low = 1;
	high = v[0];
	while(low < high)
	{
		mid = low + (high - low)/2;
		if(x > v[mid]) 
			low = mid + 1;
		if(x <= v[mid]) {
			high = mid - 1;
			sol = mid;
		}
	}
	if (v[low] >= x)
		sol = low;
	return sol;
}
 

int main()
{
	int i, *v, t, x, m;
	FILE *f = freopen("cautbin.in" , "rt", stdin);
	FILE *g = freopen("cautbin.out" , "wt" , stdout);
	scanf("%d" , &m);
	v = malloc((m + 1) * sizeof(int));
	v[0] = m;
	for(i = 1; i <= v[0]; i++)
		scanf("%d" , &v[i]);
	scanf("%d" , &m);         
	for(i = 1; i <= m; i++) {
		scanf("%d" , &t);
		scanf("%d" , &x);
		if(t == 0) {        
			printf("%d\n" , cautbin1(x, v));
		}
		if(t == 1) {
		        printf("%d\n" , cautbin2(x, v));
		}
		if(t == 2) {
		        printf("%d\n" , cautbin3(x, v));
		}
	}
	fclose(f);
	fclose(g);
	free(v);
	return 0;
}