//5
//5
//4
#include<fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[100001];
int binsearch0(int low , int high , int x){
	 int mid ;
	 while(low<=high){
		 mid=(low+high)/2;
		 if(x>=v[mid])
			 low=mid+1;
		 else
			 high=mid-1;
	 }
	 mid=(low+high)/2;
	 if(v[mid] > x) mid--;
	 if(v[mid]==x)
		 return mid;
return -1;
}
int binsearch1(int low , int high , int x){
	 int mid ;
	 while(low<high){
		 mid=(low+high)/2;
		 if(v[mid] <= x)
			 low=mid+1;
		 else
			 high=mid;
	 }
	 mid=(low+high)/2;
	 if(v[mid] > x ) mid--;
		 return mid;
}
int binsearch2(int low , int high , int x){
	 int mid ;
	 while(low<high){
		 mid=(high+low)/2;
		 if(x>v[mid])
			 low=mid+1;
		 else
			 high=mid;
	 }
	 mid=(low+high)/2;
	 if(v[mid] < x) mid++;
		 return mid;
}
int main(){
	 int n , m , i , val , tip ;
	 fin>>n;
	 for(i=1 ; i<=n ; i++)
		 fin>>v[i];
	 fin>>m;
	 while(m--){
		 fin>>tip>>val;
		 if(tip==0)
			 fout<<binsearch0(1,n,val)<<"\n";
		 else if(tip==1)
			 fout<<binsearch1(1,n,val)<<"\n";
		 else
			 fout<<binsearch2(1,n,val)<<"\n";
	 }
return 0;
}