#include<stdio.h>
	#define MAX 100001
	using namespace std;
	int N ,M , V[MAX] , t , x  ;
	
	void citire();
	void solve();
	int caut(int x , int t);
	
	int main()
	{
		citire();
		solve();
		return 0;
	}
	
	void citire()
	{
		freopen("cautbin.in" , "r"  , stdin );
		freopen("cautbin.out" , "w" , stdout );
		scanf("%d" , &N );
		for( int i = 1 ; i<= N ; ++i )
			scanf("%d" , &V[i] );
		scanf("%d" , &M);
	}
	
	void solve()
	{
		for( int i = 1 ; i<= M ; ++i )
		{
			scanf("%d%d" , &t , &x );
			printf("%d\n" , caut(x,t));
		}
	}
	
	int caut(int x , int t)
	{
		int l , r , mid ;
		l = 1 , r = N ;
		bool sw = 0;
		while(l <= r && !sw)
		{
			mid = (l+r)/2;
			if(V[mid] == x)
				sw = 1;
			else
				if(V[mid] > x)
					r = mid-1;
				else
					l = mid+1;
		}
		if(t == 0)
		{
			if(!sw)
				return -1;
			else
				while(V[mid+1]==x)mid++;
			return mid;
		}
		else
			if(t == 1)
			{
				while(V[mid] > x)mid--;
				while(V[mid+1] <= x)mid++;
				return mid;
			}
			else
			{
				while(V[mid-1] >= x)mid--;
				while(V[mid]<x)mid++;
				return mid;
			}
	}