#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include<string>

using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");

int n, i, j, m,  b, a[100005], x, y, k, o;


int main()
{
	cin>>n;
	
	for (i=1; i<=n; ++i) cin>>a[i];
	cin>>m;
	
	while(m--)
	{
		cin>>o>>b;
		if (o==0)
		{
			int x=1, y=n, k=0;
			
			while(x<=y)
			{
				int m=(x+y)/2;
				if(a[m]<=b) x=m+1;
						else y=m-1;
			}
			
			if (a[y]!=b) y=-1;
			cout<<y<<'\n';
		}
		else if (o==1)
		{
			int x=1, y=n, k=0;
			
			while(x<=y)
			{
				int m=(x+y)/2;
				if(a[m]<=b)	x=m+1;
						else y=m-1;
			}
			cout<<y<<'\n';
		}
		else if (o==2)
		{
			int x=1, y=n, k=0;
			
			while(x<=y)
			{
				int m=(x+y)/2;
				if(a[m]>=b) 	y=m-1;
				else 	x=m+1;
			}
			cout<<x<<'\n';
		}
	}
			
	return 0;
}