#include <fstream.h>
#define SIZE 100001

ifstream fi("cautbin.in");
ofstream fo("cautbin.out");

//struct {int op, x;} B[SIZE];

int A[SIZE];
int n,m;

void citire(){
     fi>>n;

     for(int i=1;i<=n;++i)fi>>A[i];

     fi>>m;
}
int cbin(int op, int x){
    int low, high, middle;
    low = 1;
    high= n;
    while(low<=high){
	 middle = (low+high)/2;

	 if(A[middle] == x){
	   if(op == 0) return middle;
	   if(op == 1) return middle-1;
	   if(op == 2) return middle+1;
	 }
	 if(A[middle] < x){
	   if(A[middle+1] > x && op == 1) return middle;

	   low = middle+1;

	 }
	 if(A[middle] > x){
	   if(A[middle-1]<x && op == 2) return middle;

	   high= middle-1;

	 }
    }
    return -1;
}

void solve(){
     int op,x;

     while(m){
	  fi>>op>>x;
	  fo<<cbin(op,x)<<"\n";
	  -- m;
     }
}

int main(){
    citire();
    solve();
    return 0;
}