#include <cstdio>

using namespace std;

int n,i,a[100010],m,t,x,pp;

int cb0(int x)
 {
      int st,dr,mij,pos;
      st=1; dr=n,pos=0;
      while (st<=dr && !pos)
        {
            mij=(st+dr)/2;
            if (a[mij]<x) st=mij+1;
               else if (a[mij]>x) dr=mij-1;
                else if (a[mij]==x && a[mij+1]==x) st=mij+1;
                 else pos=mij;

             if (st>dr) pos=st;

        }
        if (!pos) return -1;
  return pos;

 }

 int cb1(int x)
 {
      int st,dr,mij,pos;
      st=1; dr=n,pos=0;
      while (st<=dr && !pos)
        {
            mij=(st+dr)/2;
            if (a[mij]<x) st=mij+1;
               else if (a[mij]>x) dr=mij-1;
                else if (a[mij]<=x && a[mij+1]<=x) st=mij+1;
                 else pos=mij;

             if (st>dr) pos=st;

        }
        if (!pos) return -1;
  return pos;

 }

 int cb2(int x)
 {
      int st,dr,mij,pos;
      st=1; dr=n,pos=0;
      while (st<=dr && !pos)
        {
            mij=(st+dr)/2;
            if (a[mij]<x) st=mij+1;
               else if (a[mij]>x) dr=mij-1;
                else if (a[mij]>=x && a[mij-1]>=x) dr=mij-1;
                 else pos=mij;

             if (st>dr) pos=st;

        }
  if (!pos) return -1;
return pos;

 }


int main()
{
    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++)
     {
         scanf("%d %d", &t,&x);
         if (t==0) pp=cb0(x);
          else if (t==1) pp=cb1(x);
           else pp=cb2(x);
         printf("%d\n", pp);
     }

    return 0;
}