#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], b[NX][2];

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);
    for (int i = 1; i <= M; i++)
        fscanf(in, "%d %d", &b[i][0], &b[i][1]);
}

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