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


const int maxn = 100100;
using namespace std;
signed a[maxn]; 
int m,n;

int fmax(int v,int l=1,int r=n){	
	if(a[M]==v && a[M+1]!=v)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 )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)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 a1;
 a[0]=-200;
 a[n+1]=2000000000;
 unsigned b;
  for(int i=1;i<=m;i++) {
  	scanf("%d %d",&a1,&b);
  	if(a1==0){
  		printf("%d\n",fmax(b));
  	}else if(a1==1){
  		printf("%d\n",pmax(b));
  	}else{
  		printf("%d\n",pmin(b));
  	}
  }


	 
}