#include<stdio.h>
#define Nmx 100002

int n,m,a[Nmx];

void caut0(int x)
{
    int st=1,dr=n;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(a[mij]<=x)
            st=mij+1;
        else dr=mij-1;
    }
    int mij=(st+dr)/2;
    if(a[mij]>x)    mij--;
    if(a[mij]==x)
        printf("%d\n",mij);
    else printf("-1\n");
}

void caut1(int x)
{
    int st=1,dr=n;
    while(st<dr)
    {
        int mij=(st+dr)/2;
        if(a[mij]<=x)
            st=mij+1;
        else dr=mij-1;
    }
    int mij=(st+dr)/2;
    if(a[mij]>x)   mij--;
    printf("%d\n",mij);
}

void caut2(int x)
{
    int st=1,dr=n;
    while(st<dr)
    {
        int mij=(st+dr)/2;
        if(a[mij]<x)
            st=mij+1;
        else dr=mij-1;
    }
    int mij=(st+dr)/2;
    if(a[mij]<x)    ++mij;
    printf("%d\n",mij);
}

int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    scanf("%d",&m);
    int tip,x;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&tip,&x);
        if(tip==0)
            caut0(x);
        else if(tip==1)
                caut1(x);
            else caut2(x);
    }
    return 0;
}