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

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

#define MAX 500001

int v[MAX],N,M;

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

		out<<max<<'\n';
	}
	else if(op==1)
	{
	   if(v[N]<=x)
	   {
		   out<<N<<'\n';
		   return;
	   }
       do
		{
		   mid=(M+m)/2;
		  if(x>v[(M+m)/2])
			  m=mid;
		  else if(x<v[(M+m)/2])
			  M=mid;
		  else
		  {
			  max=mid;
			  if(mid<N && v[mid+1]==x)
			  {
				  m=mid+1;
				  max=m;
			  }
		  }
		}while((m+M)/2!=mid);
		if(max>=0)
		 out<<max<<'\n';
		else
		  out<<mid<<'\n';
	}
	else if(op==2)
	{
		do
		{
		   mid=(M+m)/2;
		  if(v[(M+m)/2]<x)
			  m=mid;
		  else if(x<v[(M+m)/2])
			  M=mid;
		  else
		  {
			  min=mid;
			  if(mid>1 && v[mid-1]==x)
			  {
				  m=mid-1;
				  min=m;
			  }
		  }
		}while((m+M)/2!=mid);
        if(min!=(1<<30))
		 out<<min<<'\n';
		else
		 out<<mid+1<<'\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;
}