#include <stdio.h>
int dr , st , a , x , n , m , i  , mid;
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(i=1;i<=m;i++){
		scanf("%d %d",&a,&x);
		if(a==0){
			st=1;dr=n;
			while(st<=dr){
				mid=(st+dr)/2;
				if(V[mid]<=x)
					st=mid+1;
				else
					dr=mid-1;
			}
			if(V[st]!=x)
				st--;
			if(V[st]==x)
				printf("%d\n",st);
			else
				printf("%d\n",-1);
		}
		else{
			if(a==1){
				st=1;dr=n;
				while(st<=dr){
					mid=(st+dr)/2;
					if(V[mid]<=x)
						st=mid+1;
					else
						dr=mid-1;
				}
				if(V[st]>x)
					st--;
				printf("%d\n",st);
			}
			else{
				st=1;dr=n;
				while(st<=dr){
					mid=(st+dr)/2;
					if(V[mid]<x)
						st=mid+1;
					else
						dr=mid-1;
				}
				if(V[dr]<x)
					dr++;
				printf("%d\n",dr);
			}
		}
	}
	
	
	return 0;
}