#include <cstdio>
#include <algorithm>
using namespace std;
FILE *f,*g;
int v[100100];
int n,m,x,i,mn,y,mx;

void caut1(int st,int dr,int x)
{
     if (st<=dr)
     {
          int m=st+(dr-st)/2;
          if (v[m]<=x)
          {
               if (m>mx) mx=m;
               caut1(m+1,dr,x);
          }
          else
               caut1(st,m-1,x);
     }
}

void caut2(int st,int dr,int x)
{
     if (st<=dr)
     {
          int m=st+(dr-st)/2;
          if (v[m]>=x)
          {
               if (m<mn || mn==-1) mn=m;
               caut2(st,m-1,x);
          }
          else
               caut2(m+1,dr,x);
     }
}

int main()
{
     f=fopen("cautbin.in","r");
     g=fopen("cautbin.out","w");

     fscanf(f,"%d",&n);

     for (i=1;i<=n;i++)
          fscanf(f,"%d",&v[i]);

     fscanf(f,"%d",&m);

     for (i=1;i<=m;i++)
     {
          fscanf(f,"%d%d",&y,&x);
          mx=mn=-1;
          switch (y)
          {
               case 0: caut1(1,n,x);
                       if (mx==-1 || v[mx]!=x)
                         fprintf(g,"-1\n");
                       else
                         fprintf(g,"%d\n",mx);
                       break;
               case 1: caut1(1,n,x);
                       fprintf(g,"%d\n",mx);
                       break;
               case 2: caut2(1,n,x);
                       fprintf(g,"%d\n",mn);
                       break;
          }
     }

     fclose(f);
     fclose(g);
     return 0;
}