#include <cstdio>

using namespace std;

int i, t, x, n, m, a[100005];

int bs0(int st, int dr, int val)
{
    int mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]<=val)
            st=mij+1;
        else
            dr=mij-1;
    }
    mij=(st+dr)/2;
    if(a[mij]>val)
        m--;
    if(a[mij]==val)
        return mij;
    return -1;
}

int bs1(int st, int dr, int val)
{
    int mij;
    while(st<dr)
    {
        mij=(st+dr)/2;
        if(a[mij]<=val)
            st=mij+1;
        else
            dr=mij;
    }
    mij=(st+dr)/2;
    if(a[mij]>val)
        mij--;
    return mij;
}

int bs2(int st, int dr, int val)
{
    int mij;
    while(st<dr)
    {
        mij=(st+dr)/2;
        if(a[mij]<val)
            st=mij+1;
        else
            dr=mij;
    }
    mij=(st+dr)/2;
    if(a[mij]<val)
        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", &a[i]);
    scanf("%d", &m);
    while(m--)
    {
        scanf("%d%d", &t, &x);
        if(!t)
            printf("%d\n", bs0(1, n, x));
        else if(t==1)
            printf("%d\n", bs1(1, n, x));
        else
            printf("%d\n", bs2(1, n, x));
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}