#include <stdio.h>
#include <stdlib.h>
int a[];
int cautare_bin(int,int,int);
int cautare_bin2(int,int,int);
int cautare_bin3(int,int,int);

int cautare_bin(int x,int left,int right)
{
    int i,j,p,r;
    i=left; j=right; r=(i+j)/2;
    if (i==j-1)
     {
         if (a[j]==x) return j; else
         if (a[i]==x) return i; else return -1;
     } else
    if (x>=a[r]&& x<=a[j]) cautare_bin(x,r,j); else cautare_bin(x,i,r);
}

int cautare_bin2(int x,int left,int right)
{
    int i,j,p,r;
    i=left; j=right; r=(i+j)/2;
    if (i==j-1)
     {
         if (a[j]==x) return j; else
         if (a[i]==x) return i; else return i;
     } else
    if (x>=a[r]&& x<=a[j]) cautare_bin2(x,r,j); else cautare_bin2(x,i,r);
}


int cautare_bin3(int x,int left,int right)
{
    int i,j,p,r;
    i=left; j=right; r=(i+j)/2;
    if (i==j-1)
     {
         if (a[j]==x) return j; else
         if (a[i]==x) return i; else return j;
     } else
    if (x>=a[i]&& x<=a[r]) cautare_bin3(x,i,r); else cautare_bin3(x,r,j);
}


int main()
{
    int i,n,m,k,x;
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%i",&n);
    for (i=1; i<=n; i++)
     scanf("%i",a[i]);
    scanf("%i",&m);
    for (i=1; i<=m; i++)
     {
        scanf("%i%i",k,x);
        if (k==0) fprintf("%i\n",cautare_bin(x,1,n)); else
        if (k==1) fprintf("%i\n",cautare_bin2(x,1,n)); else fprintf("%i\n",cautare_bin3(x,1,n));
     }
    return 0;
}