#include <stdio.h>
#define DIM 100011

int V[DIM];
int n,m,i,p,u,mid,x,op;

int main(){
	FILE *f = fopen("cautbin.in","r");
	FILE *g = fopen("cautbin.out","w");
	fscanf(f,"%d",&n);
	for (i=1;i<=n;i++)
		fscanf(f,"%d",&V[i]);

	fscanf(f,"%d",&m);
	for (i=1;i<=m;i++){
		fscanf(f,"%d%d",&op,&x);
		if (op==0) {
			//0 x - pozitia cea mai mare pe care se afla elementul cu valoarea x sau -1 daca nu se gaseste in sir
			p=1;u=n;
			while (p<=u) {
				mid = p+(u-p)/2;
				if (x>=V[mid])
					p = mid+1;
				else
					u = mid-1;
			}
			if (V[u]==x)
				fprintf(g,"%d\n",u);
			else
				fprintf(g,"%d\n",-1);
		} else if (op==1) {
			//1 x - pozitia pe care se afla elementul cel mai mare mai mic sau egal cu x in sir. 
			//Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x 
			p = 1; u = n;
			while (p<=u) {
				mid = p+(u-p)/2;
				if (V[mid]>x)
					u = mid-1;
				else
					p = mid+1;
			}
			fprintf(g,"%d\n",u);
		} else{
			//2 x - pozitia pe care se afla elementul cel mai mic mai mare sau egal cu x in sir. 
			//Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x
			p = 1; u = n;
			while (p<=u) {
				mid = p+(u-p)/2;
				if (V[mid]<x)
					p = mid + 1;
				else
					u = mid - 1;
			}
			fprintf(g,"%d\n",p);
		}
	}

	fclose(g);
	fclose(f);
	return 0;
}