#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 lo, int hi, int prev)
{
    if (lo == hi && a[lo] == x) return lo;
    else
        if (lo == hi && a[lo] != x) return prev;
        else
        {
            int mid = (lo + hi) / 2;
            if (a[mid] <= x)
            {
                if (a[mid + 1] > x)
                    return mid;
                else
                    return cautBin1 (x, mid + 1, hi, mid); // transmit pozitia precedenta
            }
            else
                return cautBin1 (x, lo, mid, mid);
        }
}

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

int cautBin3(int x, int lo, int hi, int prev)
{
    if (lo == hi && a[lo] >= x) return lo;
    else if (lo == hi && a[lo] < x) return prev;
        else
        {
            int mid = (lo + hi) / 2;
            if (a[mid] >= x)
                return cautBin3 (x, lo, mid, mid);
            else
                return cautBin3 (x, mid + 1, hi, 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();
    for (int i = 1; i <= M; i++)
        switch(b[i][0])
        {
            case 0: fprintf(out, "%d\n", cautBin1(b[i][1], 1, N, -1)); break;
            case 1: fprintf(out, "%d\n", cautBin2(b[i][1], 1, N, -1)); break;
            case 2: fprintf(out, "%d\n", cautBin3(b[i][1], 1, N, -1)); break;
        }
    return 0;
}