#include <stdio.h>

int n;
int v[100001];

int binary0(int x)
{
    int sol = -1,st = 1,dr = n,mij;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(v[mij] == x)
        {
            sol = mij;
            st = mij + 1;
        }
        else
            dr = mij - 1;
    }
    return sol;
}

int binary1(int x)
{
    int sol,st = 1,dr = n,mij;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(v[mij] <= x)
        {
            sol = mij;
            st = mij + 1;
        }
        else
            dr = mij - 1;
    }
    return sol;
}

int binary2(int x)
{
    int sol,st = 1,dr = n,mij;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(v[mij] >= x)
        {
            sol = mij;
            dr = mij - 1;
        }
        else
            st = mij + 1;
    }
    return sol;
}

int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    int i,st,dr,mij,m,mod,x;
    scanf("%d",&n);
    for(i = 1; i <= n; ++i)
        scanf("%d",&v[i]);
    scanf("%d",&m);
    for(i = 1; i <= m; ++i)
    {
        scanf("%d %d",&mod,&x);
        if(mod == 0)
            printf("%d\n",binary0(x));
        else
            if(mod == 1)
                printf("%d\n",binary1(x));
            else
                printf("%d\n",binary2(x));

    }
    return 0;
}