#include<iostream.h>
#include<fstream.h>  
int n,m;
int v[100000];
int caut_bin0( int value)
{   int i ;
    i = n;
	while (value <= v[i])
	{
		if( value == v[i] ) 
			return i;
        i--;
		
	}
	return -1;
		
}
int caut_bin1( int value)
{  
	int i = n;
	while (v[i] >= value) 
	{
		if( value == v[i] ) 
			return i;
		i--;
	}
    return i;
}	
int caut_bin2( int value)
{  
	int i = 1;
	while (v[i] <= value) 
	{
		if( value == v[i] ) 
			return i;
		i++;
	}
    return i;
}	
		
int main()
{   int i;
    ifstream f("cautbin.in"); 
  //  ofstream g("cautbin.out"); 
	//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();
    // g.close();        
     return 0;
     
}