#include <stdio.h>
int v[100011];

int x0(int dr, int num)
{
    int med,st;
    st=1;
    while (st<=dr)
    {
        med=(st+dr)>>1;
        if (v[med]<=num)
            st=med+1;
        else
            dr=med-1;
    }
    st=(st+dr)>>1;
    if (v[st]>num)
        st--;
    if (v[st]==num)
        return st;
    return -1;
}

int x1 (int dr, int num)
{
    int med,st;
    st=1;
    while (st<dr)
    {
        med=(st+dr)>>1;
        if (v[med]<=num)
            st=med+1;
        else
            dr=med;
    }
    st=(st+dr)>>1;
    if (v[st]>num)
       st--;
    return st;
}

int x2 (int dr, int num)
{
    int med,st;
    st=1;
    while (st<dr)
    {
        med=(st+dr)>>1;
        if (v[med]<num)
            st=med+1;
        else
            dr=med;
    }
    st=(st+dr)>>1;
    if (v[st]<num)
       st++;
    return st;
}
int main ()
{
    FILE *f1,*f2;
    int i, n, m, op, num;
    f1=fopen("cautbin.in","r");
    fscanf(f1,"%d",&n);
    for (i=1;i<=n;i++)
        fscanf(f1,"%d",&v[i]);
    fscanf(f1,"%d",&m);
    f2=fopen("cautbin.out","w");
    for (i=1;i<=m;i++)
    {
          fscanf(f1,"%d%d",&op,&num);
          if (op==0)
             fprintf(f2,"%d\n",x0(n,num));
          else
             if (op==1)
                fprintf(f2,"%d\n",x1(n,num));
             else
                if (op==2)
                    fprintf(f2,"%d\n",x2(n,num));
    }
    fclose(f1);
    fclose(f2);
    return 0;
}