#include <cstdio>
#define N 100010

int n, v[N];

int solve0(int val)
{
    int li = 1;
    int lf = n;
    int m = (li + lf) / 2;
    while (li<=lf)
    {
        if (v[m] <= val)
            li = m + 1;
        else
            lf = m - 1;
        m = (li+lf)/2;
    }
    if(lf<1)
        return -1;
    if(v[lf]==val)return lf;
    return -1;
}

int solve1(int val)
{
    int li = 1;
    int lf = n;
    int m = (li + lf) / 2;
    while (li <= lf)
    {
        if (v[m] <= val)
            li = m + 1;
        else
            lf = m - 1;
        m = (li + lf) / 2;
    }
    return lf;
}

int solve2(int val)
{
    int li = 1;
    int lf = n;
    int m = (li + lf) / 2;
    while (li <= lf)
    {
        if (v[m] >= val)
            lf = m - 1;
        else
            li = m + 1;
        m = (li + lf) / 2;
    }
    return m+1;
}

int main()
{
    int i, m, val, tip;
    FILE *fin=fopen("cautbin.in", "r");
    FILE *fout=fopen("cautbin.out", "w");
    fscanf(fin,"%d", &n);
    for (i = 1; i <= n; ++i)
        fscanf(fin,"%d", &v[i]);
    fscanf(fin,"%d", &m);
    while (m--)
    {
        fscanf(fin,"%d%d", &tip, &val);
        if (tip == 0)
            fprintf(fout,"%d\n", solve0(val));
        if (tip == 1)
            fprintf(fout,"%d\n", solve1(val));
        if (tip == 2)
            fprintf(fout,"%d\n", solve2(val));
    }
    fclose(fin);
    fclose(fout);
    return 0;
}