#include<cstdio>
#include<cstdlib>

FILE*f;
FILE*g;
int a[100000];

int caut_bin0(int st,int dr,int x)
{
     int mij;
     while (st<=dr)
     {
           mij=st+(dr-st)/2;
           if (st==mij){
              if (a[st]==x)
                 return st;
              else      
                 return -1;}
               if (a[mij]>x)
                  dr=mij;
               else
                   st=mij;}                     
}
int caut_bin1(int st,int dr,int x) //la asta mai trebuie lucrat!!
{
     int mij;
     while (st<=dr)
     {
           mij=st+(dr-st)/2;
           if (st==mij)
              if (a[st]<=x)
                 return st;
           if (a[mij]>x)
                  dr=mij;
               else
                   st=mij;}                     
}

int caut_bin2(int st,int dr,int x)
{
     int mij;
     while (st<=dr)
     {
           mij=st+(dr-st)/2;
           if ((dr==mij) || (dr==st+1))
              if (a[dr]>=x)
                 return dr;
           if (a[mij]<x)
                  st=mij;
               else
                   dr=mij;}                     
}

int main()
{
    int n,i,m,tip,x;
    f=fopen("cautbin.in","r");
    g=fopen("cautbin.out","w");
    fscanf(f,"%d",&n);
    for (i=1;i<=n;i++)
        fscanf(f,"%d",&a[i]);
    fscanf(f,"%d",&m);
    while (m)
    {
          fscanf(f,"%d%d",&tip,&x);
          switch (tip)
          {case 0:fprintf(g,"%d \n",caut_bin0(1,n,x));break;
          case 1:fprintf(g,"%d \n",caut_bin1(1,n,x));break;
          case 2:fprintf(g,"%d \n",caut_bin2(1,n,x));}
         
          m--;
          }
    return 0;
}