#include<iostream>
#include<fstream>
using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");

#define MAX 100010

int v[MAX],N,M;

void cautare_binara(int x,int op)
{
	int mid,pos=-1,m=1,M=N;
	if(op==0)
	{
		while(m<=M)
		{
			mid=(m+M)/2;
			if(v[mid]==x)
				pos=max(pos,mid);
			if(x>=v[mid])
			{
				m=mid+1;
			}
			else
				M=mid-1;
				
		}
		out<<pos<<'\n';
	}
	else if(op==1)
	{
	  while(m<=M)
		{
			mid=(m+M)/2;
			if(v[mid]<=x)
				pos=max(pos,mid);
			if(x>=v[mid])
			{
				m=mid+1;
			}
			else
				M=mid-1;
				
		}
		out<<pos<<'\n';
	}
	else if(op==2)
	{
		pos=N;
         while(m<=M)
		{
			mid=(m+M)/2;
			if(v[mid]>=x)
				pos=min(pos,mid);
			if(x<=v[mid])
			{
				M=mid-1;
			}
			else
				m=mid+1;
				
		}
		out<<pos<<'\n';
	}

}

int main()
{

	in>>N;
	int i;
	for(i=1;i<=N;i++)
		in>>v[i];
	in>>M;
	int p,v;
	for(int i=1;i<=M;i++)
	{
		in>>p>>v;

		cautare_binara(v,p);
	}

	in.close();
	out.close();

	return 0;
}