#include <stdio.h>

using namespace std;
FILE *f=fopen("cautbin.in","r");
FILE *g=fopen("cautbin.out","w");

int n,v[100005],k,t,x,i;

int bin1(int nr)
{int p=1,u=n,m,mx=0;

while (p<=u)
{
m=(p+u)/2;
if (v[m]<=nr)
{
if (v[m]==nr && m>mx)mx=m;
p=m+1;
}
else u=m-1;
}
return mx;
}

int bin2(int nr)
{int p=1,u=n,m,mx=0;

while (p<=u)
{
m=(p+u)/2;
if (v[m]<=nr)
{
if (m>mx)mx=m;
p=m+1;
}
else u=m-1;
}
return mx;
}

int bin3(int nr)
{int p=1,u=n,m,mx=99999;

while (p<=u)
{
m=(p+u)/2;
if (v[m]<nr)
p=m+1;
else {
u=m-1;
if (m<mx)mx=m;
}
}
return mx;
}



int main()
{
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
fscanf(f,"%d",&v[i]);
fscanf(f,"%d",&k);
for(i=1;i<=k;i++)
{
 fscanf(f,"%d%d",&t,&x);
 if (t==0)fprintf(g,"%d\n",bin1(x));
 if (t==1)fprintf(g,"%d\n",bin2(x));
 if (t==2)fprintf(g,"%d\n",bin3(x));

}





fclose(g);
return 0;
}