#include<iostream.h>
#include<fstream.h>  
int n,m;
int v[100000];
int caut_bin0( int value)
{   
	int st = 1, dr = n;
	while ( st != dr)
	{
		int mij = ( st + dr) /2;
		if( v[ mij ] > value)
		{
			dr = mij;
		}
		else st = mij + 1;
		
	}
	if( v[ st ] == value) return st;
	if( v[ st - 1] == value) return st-1;
	return -1;
		
}
int caut_bin1( int value)
{  
	int st = 1, dr = n;
	while (st != dr )
    {
		int mij = (st +dr ) / 2;
        if  (v[ mij ] > value) 
		    dr = mij;
        else  st = mij+1;
	}
    if ( v[ st ] <= value) return st;
    if ( v[ st - 1 ] <= value) return st-1;    
		
}	
int caut_bin2( int value)
{  
	int st=1, dr = n;
	while (st < dr-1)
	{   
		int mij = (st + dr) / 2;
        if  (v[ mij ] > value) 
		st = mij;
        else  dr = mij;
	}
	if ( v[ st - 1 ] >= value) return st - 1;
    if ( v[ st ] >= value) return st;
    if ( v[	st + 1 ] >= value) return st + 1;
}		
		
int main()
{   int i;
    ifstream f("cautbin.in"); 
 
	freopen("cautbin.out","w",stdout);
    f>>n;
    for(i = 1; i <= n; i++) 
          f>>v[i];
    f>>m;
    for(int j = 1; j <= m; j++)
	{
		int type, value;
		f>>type>>value;
		if( type == 0)
			cout<< caut_bin0( value)<<endl;
		if( type == 1)
			cout<< caut_bin1( value)<<endl;
		if( type == 2)
			cout<< caut_bin2( value)<<endl;
	}
    
   
     f.close();
         
     return 0;
     
}