#include<stdio.h>
long v[100010],n,m;

void read()
{
scanf("%ld",&n);
long i;
for (i=1;i<=n;i++)
     scanf("%ld",&v[i]);
scanf("%ld",&m);
}

long cautbin(long st,long dr,long k)
{
long w,m;
w=-1;
while (st<=dr)
      {
       m=(st+dr)/2;
       if (v[m]==k)
          {
           w=m;
           st=m+1;
          }
      else if (v[m]<k)
              {
               st=m+1;
              }
            else {
                  dr=m-1;
                 }
      }
return w;
}

long cautbin1(long st,long dr,long k)
{
long w,m;
w=-1;
while (st<=dr)
      {
       m=(st+dr)/2;
       if (v[m]<=k)
          {
           w=m;
           st=m+1;
          }
      else {
            dr=m-1;
           }
      }
return w;
}

long cautbin2(long st,long dr,long k)
{
long w,m;
w=-1;
while (st<=dr)
      {
       m=(st+dr)/2;
       if (v[m]>=k)
          {
           w=m;
           dr=m-1;
          }
      else {
            st=m+1;
           }
      }
return w;
}

void rez()
{
long a,b;
long i;
for (i=1;i<=m;i++)
    {
     scanf("%ld%ld",&a,&b);
     if (a==0)
        printf("%ld\n",cautbin(1,n,b));
      else if (a==1)
               printf("%ld\n",cautbin1(1,n,b));
           else printf("%ld\n",cautbin2(1,n,b));
    }
}

int main()
{
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);
read();
rez();
return 0;
}