#include <stdio.h>
#define M (l+(r-l)/2)


const int maxn = 100000;
using namespace std;
unsigned a[maxn]; 
int m,n;

int fmax(int v,int l=1,int r=n){	
	if(a[M]==v && (a[M+1]!=v || M+1==n))return M;
	if(l>=r)return -1;
	if(a[M]>v)return fmax(v,l,M);
	else return fmax(v,M+1,r);	
}

int pmax(int v,int l=1,int r=n){
	if(a[M]<=v && (a[M+1]>v || M+1==n ))return M;
	if(a[M]>v)return pmax(v,l,M);
	else return pmax(v,M+1,r);
}

int pmin(int v,int l=1,int r=n){
	if(a[M]>=v && (a[M-1]<v || M-1==0 ))return M;
	if(a[M]>=v)return pmin(v,l,M);
	else return pmin(v,M+1,r);
}

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);
 int a;
 unsigned b;
  for(int i=1;i<=m;i++) {
  	scanf("%d %d",&a,&b);
  	if(a==0){
  		printf("%d\n",fmax(b));
  	}else if(a==1){
  		printf("%d\n",pmax(b));
  	}else{
  		printf("%d\n",pmin(b));
  	}
  }


	 
}