#include <iostream>
#include <fstream>
using namespace std;

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

int v[100001];
int n,i,t,x,y;


int x0(int y)
{
		int mij,pMax=-1;
		int st=1;
		int dr=n;
		while(st<=dr)
		{
			mij=(st+dr)/2; 
			
		    if(y==v[mij])
			    {
					pMax=mij;
					st=mij+1;
				}	
		    else
			    if(y>v[mij])
				{
					st=mij+1;
			    }
		        
		    else
		            dr=mij-1;
		}
	return pMax;
}


int x1(int y)
{
		int mij,pMaxE;
		int dr=n;
		int st=1;
		
		while(st<=dr)
		{
			mij=(st+dr)/2; 
		
			if(v[mij]<=y)		
				{
				pMaxE=mij;
				st=mij+1;
				}
			else
		   		dr=mij-1;
		}
	return pMaxE;
}

int x2(int y) 
{
		int mij,pMinE;
		int st=1;
		int dr=n;
		
		while(st<=dr)
		{
			mij=(st+dr)/2; 
			
			if(v[mij]>=y)
			  {
			  	pMinE=mij;
				dr=mij-1;
			  }
		    else
		      st=mij+1;
		}
	return pMinE;
}


int main()
{

 		in>>n;
 		
 		
		for(i=1;i<=n;i++)
		{
			in>>v[i];
		}
    	
		in>>t;
          
		for(i=0;i<t;i++)
	    {
			 in>>x>>y;
			 switch(x)
			 {
			 	case 0:
	            out<<x0(y)<<"\n";
	            break;
	     	
	        	case 1:
	            out<<x1(y)<<"\n";
	            break;
	       
	        	case 2:
	            out<<x2(y)<<"\n";

	            	
			 }
	         
	    }           
           
		 in.close();
		out.close();
		
	return 0;
}