#include <stdio.h>
int k , x , m , st , dr , max , n , a , i , j;
int V[100009];
int main(){
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&V[i]);
	scanf("%d",&m);
	for(j=1;j<=m;j++){
		scanf("%d %d",&a,&x);
		if(a==0){
			max=-1;
			st=1;dr=n;
			while(st<=dr){
				k=(st+dr)/2;
				if(V[k]==x){
					st=k+1;
					max=k;
				}
				if(V[k]<x)
					st=k+1;
				if(V[k]>x)
					dr=k-1;
			}
			printf("%d\n",max);
		}
		else{
			if(a==1){
				st=1;dr=n;
				while(st<=dr){
					k=(st+dr)/2;
					if(V[k]<=x){
						st=k+1;
						max=k;
					}
					else
						dr=k-1;
				}
				printf("%d\n",max);
			}
			else{
				st=1;dr=n;
				while(st<=dr){
					k=(st+dr)/2;
					if(V[k]>=x){
						dr=k-1;
						max=k;
					}
					else
						st=k+1;
				}
				printf("%d",max);
			}
		}
	}
	return 0;
}