#include <cstdio>

using namespace std;
int n,v[100010],m,x,c;

int caut_bin(int nr)
{
    int st=1;
    int dr=n,mij;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (nr>=v[mij])
            st=mij+1;
        else

            dr=mij-1;
    }
    mij=(st+dr)/2;
    if (v[mij]<nr)
        mij--;
    if (v[mij]==nr)
        return mij;
    return -1;

}

int caut_bin_1(int nr)
{
    int st=1;
    int dr=n,mij;
    while (st<dr)
    {
        mij=(st+dr)/2;
        if (v[mij]<=nr)
            st=mij+1;
        else
            dr=mij;
    }

    mij=(st+dr)/2;

    if (v[mij]>x)
        mij--;

    return mij;

}

int caut_bin_2(int nr)
{
    int st=1;
    int dr=n;
    int mij=(st+dr)/2;
    while (st<dr)
    {
        mij=(st+dr)/2;
        if (v[mij]<nr)
            st=mij+1;
        else

            dr=mij;


    }
    mij=(st+dr)/2;

    if (v[mij]<x)
        mij++;
    return 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",&v[i]);
    scanf("%d",&m);
    for (int j=1; j<=m; ++j)
    {
        scanf("%d%d",&c,&x);
        if (c==0)
        {
            printf("%d\n",caut_bin(x));
            continue;
        }

        if (c==1)
        {
            printf("%d\n",caut_bin_1(x));
            continue;
        }
        if (c==2)
        {
            printf("%d\n",caut_bin_2(x));

        }
    }

    return 0;
}