#include <iostream>
#include <fstream>
#include <stdlib.h>

using namespace std;

#define NX 100005

FILE *in = fopen("cautbin.in", "r");
FILE *out = fopen("cautbin.out", "w");
int N, M, a[NX];

int cautBin1(int x)
{
    int p = 1, u = N, retVal = -1, m;
    while (p <= u)
    {
        m = (p + u) / 2;
        if (a[m] <= x)
        {
            if (a[m] == x)
                retVal = m;
            p = m + 1;
        }
        else
        {
            u = m - 1;
        }
    }

    return retVal;
}

int cautBin2(int x)
{
    int p = 1, u = N, retVal = -1, m;
    while (p <= u)
    {
        m = (p + u) / 2;
        if (a[m] <= x)
        {
            retVal = m;
            p = m + 1;
        }
        else
        {
            u = m - 1;
        }
    }

    return retVal;
}

int cautBin3(int x)
{
    int p = 1, u = N, retVal = -1, m;
    while (p <= u)
    {
        m = (p + u) / 2;
        if (a[m] >= x)
        {
            retVal = m;
            u = m - 1;
        }
        else
        {
            p = m + 1;
        }
    }

    return retVal;
}

void cit()
{
    fscanf(in, "%d", &N);
    for (int i = 1; i <= N; i++)
        fscanf(in, "%d", &a[i]);
    fscanf(in, "%d", &M);
}

int main()
{
    int intr, val;
    char v[20];
    v[0] = 0;
    cit();
    for (int i = 1; i <= M; i++)
    {
        fscanf(in, "%d %d", &intr, &val);
        switch(intr)
        {
            case 0: fprintf(out, "%d\n", cautBin1(val)); break;
            case 1: fprintf(out, "%d\n", cautBin2(val)); break;
            case 2: fprintf(out, "%d\n", cautBin3(val)); break;
        }
    }
    return 0;
}