#include<stdio.h>

long n,m,v[100000];

void read()
{
long i;
scanf("%ld",&n);
for(i=1;i<=n;++i)
   scanf("%ld",&v[i]);
}

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

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


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

}

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

long i,b,c;
int a;

read();

scanf("%ld",&m);

for(i=1;i<=m;++i)
   {
   scanf("%d%ld",&a,&b);
   if(a==0)
     {
     b=bs0(b);
     printf("%ld\n",b);
     }
     else
        {
        if(a==1)
          {
          c=b;
          b=bs1(b);
          if(v[b]==c)
             printf("%ld\n",b);
          else
             printf("%ld\n",b-1);
          }
        else
          {
          c=b;
          b=bs2(b);
          if(v[b-1]==c)
             printf("%ld\n",b-1);
          else
             printf("%ld\n",b);
          }
        }
   }

return 0;
}