#include <stdio.h>

int n, i, t, q, x;
int a[100001];

int main()
{
    FILE* f=fopen("cautbin.in", "r");
    FILE* g=fopen("cautbin.out", "w");

    fscanf(f, "%d\n", &n);
    for (i = 1; i <= n; i++)
        fscanf(f, "%d ", &a[i]);
    fscanf(f, "%d\n", &t);
    for(;t;t--)
    {
        fscanf(f, "%d %d\n", &q, &x);
        if (q == 0)
        {
            int st = 1, dr = n;
            int m;
            while (st <= dr)
            {
                m = (st+dr)/2;
                if (a[m] <= x)
                    st = m+1;
                else
                    dr = m-1;
            }
            if (a[m] > x) m--;
            if (a[m] == x)
                fprintf(g,"%d\n", m);
            else
                fprintf(g,"-1\n");
        }
        else if (q == 1)
        {
            int st = 1, dr = n;
            int m;
            while (st < dr)
            {
                m = (st+dr)/2;
                if (a[m] <= x)
                    st = m+1;
                else
                    dr = m;
            }
            if (a[m] > x)
                m--;
            fprintf(g,"%d\n", m);
        }
        else if (q == 2)
        {
            int st = 1, dr = n;
            int m;
            while (st < dr)
            {
                m = (st+dr)/2;
                if (a[m] < x)
                    st = m+1;
                else
                    dr = m;
            }
            if (a[m] < x)
                m++;
            fprintf(g,"%d\n", m);
        }
    }
    return 0;
}