#include <stdio.h>
#include <stdlib.h>

int v[100000];

int cautbin0(int n, int x)
{
    if ( v[n] == x ){
        return n;
    }

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

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

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

int main()
{
    FILE *fin, *fout;
    fin = fopen ("cautbin.in", "r");
    fout = fopen ("cautbin.out", "w");
    int n, p, c, x, i, d;
    fscanf(fin, "%d", &n);
    for (i = 1; i <= n; i++)
        fscanf(fin, "%d", &v[i]);
    fscanf(fin, "%d", &p);
    for (i = 0; i < p; i++)
    {
        fscanf(fin, "%d%d", &c, &x);
        if (c == 0)
        {
            d = cautbin0(n, x);
            fprintf(fout, "%d\n", d);
        }
        if (c == 1)
        {
            d = cautbin1(n, x);
            fprintf(fout, "%d\n", d);
        }
        if (c == 2)
        {
            d = cautbin2(n, x);
            fprintf(fout, "%d\n", d);
        }
    }

    fclose (fin);
    fclose (fout);
    return 0;
}