#include<iostream>
#include<fstream>
#define nmax 100010
#define mmax 100010
int a[nmax];
int main()
{
	std::ifstream f("cautare.in");
	std::ofstream g("cautare.out");
	int n,m,i,l,r,x,y,k,mid;
	f>>n;
	for( i=1; i<=n; i++ )
		f>>a[i];
	f>>m;
	while ( m-- )
	{ 
		f>>x>>y;
		if( !x ) 
		{	l=1; r=n;
			k=-1;	//pozitia
			while( l<r )
			{	mid=( l+r )/2 ;
				if( a[mid] == y ) 
				{
					k=mid;
					l=mid;
					if( l+1 == r ) { l=r; if (a[l] == y ) k=l; }
				}
				else if(a[mid] < y ) 
						if( l+1 == r ) { l=r; if( a[l]==y ) k=l; }
							else l=mid;
				else if(a[mid] > y ) 
						if( l+1 == r ) { l=r; if( a[l]==y ) k=l; }
							else r=mid;
			}
		g<<k<<" ";
		}
		else
				if( x==1 )
				{	
					l=1; r=n;
					k=1;
					while ( l < r )
					{
					 mid=(l+r)/2;	
						if( a[mid] == y )
						{
							k=mid;
							l=mid;
							if( l+1 == r ) { l=r; if( a[l] == y ) k=l;}
						}
						else
							if(a[mid] < y ) 
								if( l+1 == r ) {k=mid; 
												l=r; 
												if( a[l]<=y ) 	
													k=l; 
												}
										else { l=mid; k=mid; }
						else if(a[mid] > y ) 
								if( l+1 == r ) { k=mid;
												l=r; 
												if( a[l]<=y )
													k=l; 
												}
									else { r=mid; k=mid; }
				    }
				g<<k<<" ";
			    }
			else
			{
				if( x== 2 )
				{
					l=1; r=n;
					k=1;
					while ( l < r )
					{
					 mid=(l+r)/2;	
						if( a[mid] == y )
						{
							k=mid;
							r=mid;
							if( l+1 == r ) { r=l; if( a[l] == y ) k=l;}
						}
						else
							if(a[mid] < y ) 
								if( l+1 == r ) {k=mid; 
												l=r; 
												if( a[l]<=y ) 	
													k=l; 
												}
										else { l=mid; k=mid; }
						else if(a[mid] > y ) 
								if( l+1 == r ) { k=mid;
												l=r; 
												if( a[l]<=y )
													k=l; 
												}
									else { r=mid; k=mid; }
						}
				g<<k<<" ";
			 }   
		}
	}
return 0;
}