#include<iostream>
#include<fstream>
using namespace std;
int v[100001],n;
int cz(int y,int st,int dr)
{int mij,max=-1;
while(st<=dr)
{mij=(st+dr)/2;
	if(y==v[mij])
	{max=mij;st=mij+1;}
	else
		if(y>v[mij])
		st=mij+1;
else
	dr=mij-1;}
return max;
}
int c1(int y,int st,int dr)
{int mij,min;
while(st<=dr)
{mij=(st+dr)/2;
if(v[mij]<=y)
{min=mij;st=mij+1;}
else
	dr=mij-1;
}
return min;
}
int c2(int y,int st,int dr)
{int mij,min;
while(st<=dr)
{mij=(st+dr)/2;
if(v[mij]>=y)
  {min=mij;dr=mij-1;}
  else
	  st=mij+1;
}
return min;
}
int main()
{int i,l,x,y;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
f>>n;
for(i=1;i<=n;i++)
	f>>v[i];
f>>l;
//cout<<cz(l,1,n)<<" "<<c1(l,1,n)<<" "<<c2(l,1,n);
for(i=1;i<=l;i++)
	{f>>x>>y;
     if(x==0)
		 g<<cz(y,1,n)<<endl;
	 else
		 if(x==1)
			 g<<c1(y,1,n)<<endl;
		 else
			 if(x==2)
				 g<<c2(y,1,n)<<endl;
	}			 
		 
f.close();
g.close();
	return 0;
}