#include<stdio.h>
#define LMAX 100000

long n,m,v[LMAX];

long bs0(long x)
{
long st,dr,m;
st=1;
dr=n;
while(st<=dr)
     {
     m=st+(dr-st)/2;
     if(v[m]==x)
       return m;
     if(v[m]<x)
       st=m+1;
     else
       dr=m-1;
     }
return -1;
}

long bs1(long x)
{
long st,dr,m,poz=0;
st=1;
dr=n;
while(st<=dr)
     {
     m=st+(dr-st)/2;
     if(v[m]<=x)
       {
       poz=m;
       st=m+1;
       }
     else
       dr=m-1;
     }
return poz;
}

long bs2(long x)
{
long st,dr,m,poz=n+1;
st=1;
dr=n;
while(st<=dr)
     {
     m=st+(dr-st)/2;
     if(x<=v[m])
       {
       poz=m;
       dr=m-1;
       }
     else
       st=m+1;
     }
return poz;
}

void read()
{
long i,x,r;
int o;

scanf("%ld",&n);
for(i=1;i<=n;++i)
   scanf("%ld",&v[i]);

scanf("%ld",&m);
for(i=1;i<=m;++i)
   {
   scanf("%d%ld",&o,&x);
   if(o==0)
     {
     r=bs0(x);
     printf("%ld\n",r);
     }
   else
     if(o==1)
       {
       r=bs1(x);
       printf("%ld\n",r);
       }
     else
       {
       r=bs2(x);
       printf("%ld\n",r);
       }
   }
}

int main()
{
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);

read();

return 0;
}