#include <stdio.h>

using namespace std;
int a[100010],n,op,val,m;

int caut0( int s,int d,int k)
{int m ;
     while(s<=d)
     {
          m=(s+d)/2;
          if (a[m]<=k)
          s=m+1;
          else
          d=m-1;
     }
  m=(s+d)/2;
  if (a[m]>k)
  m=m-1;
  if (a[m]==k)
  return m;
  else
  return -1;
 }

int caut1(int s,int d,int k)
{
     int m;
     while(s<d)
     {
          m=(s+d)/2;
          if (a[m]<=k)
          s=m+1;
          else
          d=m;
     }
m=(s+d)/2;
if (a[m]>k)
   m--;
return m;
}

int caut2(int s,int d,int k)
{
int m;
     while(s<d)
     { m=(s+d)/2;
       if (a[m]<k)
       s=m+1;
       else
       d=m;

     }
m=(s+d)/2;
if (a[m]<k)
m++;
return m;

}


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

 scanf("%d",&n);
 for(int i=1;i<=n;++i)
   scanf("%d",&a[i]);
 scanf("%d",&m);
 for(int i=1;i<=m;++i)
  {
       scanf ("%d%d",&op,&val);
       if (op==0)
       printf("%d \n",caut0(1,n,val));
       if (op==1)
       printf("%d \n",caut1(1,n,val));
       if (op==2)
       printf("%d \n",caut2(1,n,val));
  }
 return 0;
}