#include <iostream>
#include <fstream>
#define dMAX 100010

using namespace std;

int n, pos;
unsigned int m, choice, temp;
unsigned int arr[dMAX];
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

void DefaultBinarySearch(int left, int right, unsigned int key, int &position) {

    if (left > right) {
        return;
    }
    else {
        int middle = left + (right - left) / 2;

        if (arr[middle] == key) {
            position = middle + 1;
            DefaultBinarySearch(middle + 1, right, key, position);
        }
        else {
            if (key < arr[middle]) DefaultBinarySearch(left, middle - 1, key, position);
            else DefaultBinarySearch(middle + 1, right, key, position);
        }
    }

}

void FirstBinarySearch(int left, int right, unsigned int key, int &position) {
    if (left > right) return;
    else {
        int middle = left + (right - left) / 2;
        if (arr[middle] <= key) {
            position = middle + 1;
            FirstBinarySearch(middle + 1, right, key, position);
        }
        else FirstBinarySearch(left, middle - 1, key, position);
    }
}

void LastBinarySearch(int left, int right, unsigned int key, int &position) {
    if (left > right) return;
    else {
        int middle = left + (right - left) / 2;
        if (arr[middle] >= key) {
            position = middle + 1;
            LastBinarySearch(left, middle - 1, key, position);
        }
        else LastBinarySearch(middle + 1, right, key, position);
    }
}

int main()
{
    int i, j;
    fin >> n;
    for (i = 0; i < n; i++) {
        fin >> arr[i];
    }
    //cout << DefaultBinarySearch(0, n - 1, 3, pos);
    //cout << "\n" << pos;
    fin >> m;
    for (i = 0; i < m; i++) {
        fin >> choice >> temp;
        switch (choice) {
            case 0:
                pos = -1;
                DefaultBinarySearch(0, n, temp, pos);
                fout << pos << "\n";
                break;
            case 1:
                pos = 1;
                FirstBinarySearch(0, n, temp, pos);
                fout << pos << "\n";
                break;
            case 2:
                pos = 1;
                LastBinarySearch(0, n, temp, pos);
                fout << pos << "\n";
                break;
        }
    }
    return 0;
}