#include<stdio.h>

int v[100000],n,m,x;

int binker0(int b,int j)
{
    if(b<j)
    {
        int k=(b+j)/2;
        if(v[k]==x) return k;
        if(x<v[k]) return binker0(b,k-1);
        else binker0(k+1,j);
    }
    else if(v[b]==x) return b;
         else return -1;
}

int binker1(int b,int j)
{
    if(b<j)
    {
        int k=(b+j)/2;
        if(v[k]==x) return k;
        if(x<v[k]) return binker1(b,k-1);
        else return binker1(k+1,j);
    }
    else return b;
}

int binker2(int b,int j)
{
    if(b<j)
    {
        int k=(b+j)/2;
        if(v[k]==x) return k;
        if(x<v[k]) return binker2(b,k-1);
        else return binker2(k+1,j);
    }
    else return b;
}

int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);

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

    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        int c;
        scanf("%d %d", &c,&x);
        if(c==0) printf("%d\n",binker0(1,n));
        else if(c==1) printf("%d\n",binker1(1,n));
             else if(c==2) printf("%d\n",binker2(1,n));
    }
    return 0;
}