#include <fstream.h>
#define SIZE 100001

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


long A[SIZE];

long 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, val;
    low = 1;
    high= n;
    while(low<=high){
	 middle = low + (high-low)/2;

	 if(A[middle] == x){
	   if(op == 1 && A[middle-1] == x) high = middle-1;
	   else if(op == 1) return middle;

	   if(op == 2 && A[middle+1] == x) low  = middle+1;
	   else if(op == 2) return middle;


	   if(op==0 && A[middle+1] == x) low = middle+1;
	   else if(op == 0) return middle;

	 }
	 if(A[middle] < x)

	   low = middle+1;

	 if(A[middle] > x)

	   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;
}