#include<stdio.h>
int bin0(int);
int bin1(int);
int bin2(int);
int n,a[100000],m;
int main(){
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++){int x,y;
		      scanf("%d %d",&x,&y);
		      if(x==0)printf("%d\n",bin0(y));
		      else if(x==1)printf("%d\n",bin1(y));		       
			   else printf("%d\n",bin2(y));}
return 0;}
int bin0(int y){int i,s;
		for(s=1;s<n;s<<=1);
		for(i=0;s;s>>1)if(i+s<n&&a[i+s]==y)i+=s;
		if(i==0)return -1;
		else return i;}
int bin1(int y){int i,s;
		for(s=1;s<n;s<<=1);
		for(i=0;s;s>>1)if(i+s<n&&a[i+s]<=y)i+=s;
		return i;}
int bin2(int y){int i,s;
		for(s=1;s<n;s<<=1);
		for(i=0;s;s>>1)if(i+s<n&&a[i+s]>=y)i+=s;
		return i;}