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

using namespace std;

#define NX 100005

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

int cautBin1(int x, int lo, int hi)
{
    if (lo > hi)
    {
        int mid = (lo + hi) / 2;
        if (a[mid] > x) mid--;
        if (a[mid] == x)
            return mid;
        return -1;
    }
    else
    {
        int mid = (lo + hi) / 2;
        if (a[mid] <= x)
            return cautBin1(x, mid + 1, hi);
        else
            return cautBin1(x, lo, mid - 1);
    }
}

int cautBin2(int x, int lo, int hi)
{
    if (lo >= hi)
    {
        int mid = (lo + hi) / 2;
        if (a[mid] > x) mid--;
        return mid;
    }
    else
    {
        int mid = (lo + hi) / 2;
        if (a[mid] <= x)
            return cautBin2(x, mid + 1, hi);
        else
            return cautBin2(x, lo, mid);
    }
}

int cautBin3(int x, int lo, int hi)
{
    if (lo >= hi)
    {
        int mid = (lo + hi) / 2;
        if (a[mid] < x) mid++;
            return mid;
    }
    else
    {
        int mid = (lo + hi) / 2;
        if (a[mid] < x)
            return cautBin3(x, mid + 1, hi);
        else
            return cautBin3(x, lo, mid);
    }
}

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();
    int case1 = 0, case2 = 0;
    for (int i = 1; i <= M; i++)
        switch(b[i][0])
        {

            case 0: fprintf(out, "%d\n", cautBin1(b[i][1], 1, N)); break;
            case 1: fprintf(out, "%d\n", cautBin2(b[i][1], 1, N)); break;
            case 2: fprintf(out, "%d\n", cautBin3(b[i][1], 1, N)); break;
        }
    return 0;
}