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

int a[100001];

int cautare_bin(int x,int left,int right)
{
    int i,j,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
    if (x>=a[i] && x<=a[r]) cautare_bin(x,i,r); else return -1;
}

int cautare_bin2(int x,int left,int right)
{
    int i,j,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
    if (x>=a[i] && x<=a[r]) cautare_bin2(x,i,r); else return j;
}


int cautare_bin3(int x,int left,int right)
{
    int i,j,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
    if (x>=a[r] && x<=a[j]) cautare_bin3(x,r,j); else return i;
}


int main()
{
    int n,i,j,m,el1,el2;
    FILE *f=fopen("cautbin.in","r");
    FILE *g=fopen("cautbin.out","w");
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
        fscanf(f,"%d",&a[i]);
    fscanf(f,"%d",&m);
    for(j=0;j<m;j++)
    {
        fscanf(f,"%d %d",&el1,&el2);
        if(el1==0)
            fprintf(g,"%d\n",cautare_bin(el2,1,n));
        if(el1==1)
            fprintf(g,"%d\n",cautare_bin2(el2,1,n));
        if(el1==2)
            fprintf(g,"%d\n",cautare_bin3(el2,1,n));
    }
return 0;
}