#include <cstdio>
#define N 100010

int n;
int v[N];

inline void citire() {
	scanf("%d",&n);
	
	for(int i=1; i<=n; ++i) {
		scanf("%d",&v[i]);
	}
}

inline int caut0(int x) {
	int p = 1, u = n, ret = -1, mij;
	
	while(p<=u) {
		mij = (p+u)>>1;
		
		if(x==v[mij]) {
			ret = mij;
			p = mij+1;
		} else
		if(x<v[mij]) {
			u = mij-1;
		} else {
			p = mij+1;
		}
	}
	
	return ret;
}

inline int caut1(int x) {
	int p = 1,u = n, ret = 1, mij;
	
	while(p<=u) {
		mij = (p+u)>>1;
		
		if(x>=v[mij]) {
			ret = mij;
			p = mij+1;
		} else {
			u = mij-1;
		}
	}
	
	return ret;
}

inline int caut2(int x) {
	int p = 1, u = n, ret = 1, mij;
	
	while(p<=u) {
		mij = (p+u)>>1;
		
		if(x<=v[mij]) {
			ret = mij;
			u = mij-1;
		} else {
			p = mij+1;
		}
	}
	
	return ret;
}

inline void rezolva() {
	int m, code, x;
	int (*caut[])(int) = {
		&caut0,
		&caut1,
		&caut2,
	};
	
	for(scanf("%d",&m); m>0; --m) {
		scanf("%d%d",&code,&x);
		printf("%d\n",(*caut[code])(x));
	}
}

int main() {
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	
	citire();
	rezolva();
	
	return 0;
}