#include <cstdio>
#define N 100002

int v[N];

int solve0(int p, int u, int val)
{
    int mid, st=p, dr=u;

    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(v[mid]<=val)
        {
            st=mid+1;
        }
        else
        {
            dr=mid-1;
        }
    }
    mid=(st+dr)/2;
    if(v[mid]>val) mid--;
    if(v[mid]==val)
        return mid;
    return -1;
}

int solve1(int p, int u, int val)
{
    int mid, st=p, dr=u;

    while(st<dr)
    {
        mid=(st+dr)/2;
        if(v[mid]<=val)
        {
            st=mid+1;
        }
        else
        {
            dr=mid;
        }
    }

    mid=(st+dr)/2;
    if(v[mid]>val) mid--;
    return mid;
}

int solve2(int p, int u, int val)
{
    int mid, st=p, dr=u;

    while(st<dr)
    {
        mid=(st+dr)/2;
        if(v[mid]<val)
        {
            st=mid+1;
        }
        else
        {
            dr=mid;
        }
    }
    mid=(st+dr)/2;
    if(v[mid]<val) mid++;
    return mid;
}

int main()
{
    int n,m,tip,x;

    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);
    while(m)
    {
        scanf("%d%d", &tip, &x);
        if(tip == 0)
            printf("%d\n", solve0(1,n,x));
        if(tip == 1)
            printf("%d\n", solve1(1,n,x));
        if(tip == 2)
            printf("%d\n", solve2(1,n,x));
        m--;
    }
    return 0;
}