#include <cstdio>
using namespace std;
int n,a[100001];
inline int f0(int x){
	int st=1,dr=n,rez = -1,m;
	while(st<=dr){
		m = st+(dr-st)/2;
		if(a[m]<x)
				 st = m+1;
		else
			if( a[m] > x)
				dr= m-1;
			else
				return m;
	}
	return rez;
}
inline int f1(int x){
	int st=1,dr=n,rez,m;
	while(st<=dr){
	  m = st+(dr-st)/2;
		if(a[m]<=x)
			rez = m, st= m+1;
		else
			dr = m-1;
	}
	return rez;
}
inline int f2(int x){
	int st=1,dr=n, rez , m;
	while(st<=dr){
		m =st+(dr-st)/2;
		if(a[m]>=x)
			rez = m , dr = m-1;
		else
			st = m+1;

	}
	return rez;
}
int main(){
	freopen("cautbin.in","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",a+i);
	int m;
	scanf("%d", &m);
	freopen("cautbin.out","w",stdout);
	for( ; m ; --m){
		int c,x;
		scanf( "%d%d", &c, &x);
		switch(c){
			case 0:printf("%d\n",f0(x));break;
			case 1:printf("%d\n",f1(x));break;
			case 2:printf("%d\n",f2(x));break;
		}
	}
	return 0;
}