#include <stdio.h>

int v[100100],n,m,a,x,i;

int bs1(int x)
{
    int poz,ls,ld,mij;
    ls=1;
    ld=n;
    while (ls<=ld)
    {
       mij=(ls+ld)>>1;
       if (v[mij]==x) return mij;
       if (v[mij]<x)
           {
                ls=mij+1;
            }
           else
           {
                ld=mij-1;
            }
    }
    if (v[mij]!=0) return -1;
     return mij;
}

int bs2(int x)
{
    int ls,ld,mij;
    ls=1;
    ld=n;
    while (ls<ld)
    {
        mij=(ls+ld)>>1;
        if (v[mij]<x)
            {
                ls=mij+1;
            }
            else
            {
                ld=mij;
            }
    }
    mij=(ls+ld)>>1;
    if (v[mij]>x) mij--;
    return mij;
}    

int bs3(int x)
{
    int ld,ls,mij;
    ls=1;
    ld=n;
    while (ls<ld)
    {
        mij=(ls+ld)>>1;
        if (v[mij]<x) 
            {
                ls=mij+1;
            }
            else
            {
                ld=mij;
            }
    }
    mij=(ls+ld)>>1;
    if (v[mij]<x) mij++;
    return mij;
}    

int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d", &n);
    for (i=1;i<=n;++i)
    scanf("%d", &v[i]);
    scanf("%d", &m);
    while(m--)
    {
        scanf("%d %d", &a,&x);
        if (a==0) printf("%d\n", bs1(x));
        if (a==1) printf("%d\n", bs2(x));
        if (a==2) printf("%d\n", bs3(x));
    }
    return 0;
}