#include <fstream>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int binary_search_type_0(int n1, int v1[],int x1) {
    int st = 1;
    int dr = n1;
    int found = 0;
    int mid;

    while (st <= dr && !found) {

        mid = (st + dr) / 2;

        if (x1 == v1[mid])
            if (x1 == v1[mid + 1])
                st = mid + 1;
        else {
            found = 1;
            return mid;
        }
        else
            if (x1 < v1[mid])
                dr = mid - 1;
            else
                st = mid + 1;
    }

    if (found == 0)
        return -1;
}

int binary_search_type_1(int n2, int v2[],int x2) {

    int prevNumber = x2;

    if (binary_search_type_0(n2,v2,x2) != -1)
        return binary_search_type_0(n2, v2, x2);
    else
        while (binary_search_type_0(n2, v2, prevNumber) == -1)
            prevNumber--;

    return binary_search_type_0(n2, v2, prevNumber);
}

int binary_search_type_0_reverse(int n3, int v3[],int x3) {
    int st = 1;
    int dr = n3;
    int found = 0;
    int mid;

    while (st <= dr && !found) {

        mid = (st + dr) / 2;

        if (x3 == v3[mid])
            if (x3 == v3[mid - 1])
                dr = mid - 1;
        else {
            found = 1;
            return mid;
        }
        else
            if (x3 < v3[mid])
                dr = mid - 1;
            else
                st = mid + 1;
    }

    if (found == 0)
        return -1;
}

int binary_search_type_2(int n4, int v4[],int x4) {

    int nextNumber = x4;

    if (binary_search_type_0(n4,v4,x4) != -1)
        return binary_search_type_0_reverse(n4, v4, x4);
    else
        while (binary_search_type_0_reverse(n4, v4, nextNumber) == -1)
            nextNumber++;

    return binary_search_type_0_reverse(n4, v4, nextNumber);
}

int N;
int v[100001];
int M;
int typeOfQestion;
int x;


int main()
{
    fin >> N;
    for (int i = 1; i <= N; i++)
        fin >> v[i];
    fin >> M;
    for (int j = 1; j <= M; j++) {
        fin >>typeOfQestion >> x;
        switch (typeOfQestion) {
            case 0:
                fout << binary_search_type_0(N,v,x) << '\n';
                break;
            case 1:
                fout << binary_search_type_1(N,v,x) << '\n';
                break;
            case 2:
                fout << binary_search_type_2(N,v,x) << '\n';
                break;
        }
    }



    return 0;
}