#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)/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=-1;
st=1;
dr=n;
while(st<=dr)
     {
     m=(st+dr)/2;
     if(v[m]==x)
       {
       poz=m;
       break;
       }
     if(v[m]<x)
       st=m+1;
     else
       dr=m-1;
     }
if(poz!=-1)
  {
  for(st=poz;st>=1 && v[st]==v[poz];--st);
  ++st;
  }
return st;
}

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

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;
}