#include<fstream>
#include<algorithm>
#include<vector>

#define NMAX 100005

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,v[NMAX],m;
	int mid;
int x;
int search(  void )
{
	int lo=1;
	int hi=n;
	while(lo < hi)
	{
		mid=lo+(hi-lo)/2;
		if( v[mid] <= x)
			lo=mid+1;
		else
			hi=mid-1;
		
		
	}
	if(v[mid] > x )
		--mid;
	else
		++mid;
	if(v[mid] == x )
		return mid;
	return -1;
	
}
int search1(void)
{
	int lo=1;
	int hi=n;
	while(lo < hi )
	{
		mid=lo+(hi-lo)/2;
		if( v[ mid ]  <= x )
			lo=mid+1;
		else
			hi=mid;
		
	}
	if( lo == hi)
		mid=lo;
	if(v[mid]  > x)
		--mid;
	if( v[ mid] <= x)
		return mid;
	
	
	return 0;
	
	
}

int search2( void )
{
	int lo=1;
	int hi=n;
	
    while(lo < hi )
	{
		mid=lo +(hi-lo)/2;
		if(v[mid] < x)
			lo=mid+1;
	else
		    hi=mid;
		
	}
	if( lo == hi )
		mid=hi;
	
	
		return mid;
	
	
}


int main()
{
	f>>n;
	for(int i=1; i <= n ; i++)
    {
		f>>v[i];
		
	}
	
		
	f>>m;
    int tip;
	
   
	while(m--)
	{
		
	   f>>tip>>x;
	   
	   int t;
        if( tip == 0 )		
			t=search( );
		else
			if( tip == 1)
				t=search1();
			else
				t=search2();
		g<<t<<"\n";
		
		
	}
	
	
	
	
}