#include <stdio.h>
#include <stdlib.h>

int n,m;
int a[100005];

int cautarebinara0(int prim,int ultim,int inf)
{
    int mijloc;
      while (prim<=ultim)
      {
          mijloc=(prim + ultim)/2;
          if (a[mijloc]<=inf)
              prim=mijloc+1;
              else
              ultim=mijloc-1;
      }

     mijloc=(prim + ultim)/2;
     if (a[mijloc]>inf)
           mijloc--;

     if (a[mijloc]==inf)
         return(mijloc);
     return(-1);

}

int cautarebinara1(int prim,int ultim,int inf)
{
    int mijloc;
      while (prim<ultim)
      {
          mijloc=(prim + ultim)/2;
          if (a[mijloc]<=inf)
              prim=mijloc+1;
              else
              ultim=mijloc;
      }

     mijloc=(prim + ultim)/2;
     if (a[mijloc]>inf)
           mijloc--;

     return(mijloc);
}

int cautarebinara2(int prim,int ultim,int inf)
{
    int mijloc;
      while (prim<ultim)
      {
          mijloc=(prim + ultim)/2;
          if (a[mijloc]<inf)
              prim=mijloc+1;
              else
              ultim=mijloc;
      }

     mijloc=(prim + ultim)/2;
     if (a[mijloc]<inf)
           mijloc++;

     return(mijloc);
}


int main()
{
    int i;
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);

    for (i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
    }

    scanf("%d",&m);

    for (i=1; i<=m; i++)
    {
        int x,y;

        scanf("%d %d",&x,&y);

        switch(x)
        {
            case 0: printf("%d\n",cautarebinara0(1,n,y));
                break;
            case 1: printf("%d\n",cautarebinara1(1,n,y));
                break;
            case 2: printf("%d\n",cautarebinara2(1,n,y));
                break;
            default : printf("error\n");
        }

    }
    return 0;
}