#include <iostream>
#include <fstream>

using namespace std;

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

const int nmax=100000;
int n,m,a[nmax];

void cb(int x,double y){
int left=1, right=n,mid=n/2;
if(x==0){
	while(left < right){
		
	
		if(a[mid]<=y){
			left=mid+1;
			mid=(left + right)/2;
		}
		if(a[mid]>y){
			right=mid-1;
			mid=(left + right)/2;
		}
	}
	    if(a[mid]>y)mid--;
		if(a[mid]==y){
			out <<mid<<"\n";
		}else out <<-1<<"\n";
}
if(x==1){
		while(left < right){
		
	
		if(a[mid]<=y){
			left=mid+1;
			mid=(left + right)/2;
		}
		if(a[mid]>y){
			right=mid;
			mid=(left + right)/2;
		}
	}
	    if(a[mid]>y)mid--;
		if(a[mid]<=y){
			out <<mid<<"\n";
		}
}
if(x==2){
		while(left < right){
		if(a[mid]<y){
			left=mid+1;
			mid=(left + right)/2;
		}else {
			right=mid;
			mid=(left + right)/2;
		}
	}
	    if(a[mid]<y)mid++;
		
		out <<mid<<"\n";
		
}
	
}

int main(){
in >>n;
for(int i=1;i<=n;i++)
  in>>a[i];
  
  in >>m;
for(int i=1;i<=m;i++){
  int x,y; 
	in >>x>>y;
	cb(x,y);
 }
 
return 0;
}