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

using namespace std;

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

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

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

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

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

int LastBinarySearch(int left, int right, unsigned int key, unsigned int &position) {
    if (left > right) return -1;
    int middle = left + (right - left) / 2;
    if (arr[middle] >= key) {
        position = middle + 1;
        return LastBinarySearch(left, middle - 1, key, position);
    }
    return 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;
        pos = -1;
        switch (choice) {
            case 0:
                DefaultBinarySearch(0, n, temp, pos);
                fout << pos << "\n";
                break;
            case 1:
                FirstBinarySearch(0, n, temp, pos);
                fout << pos << "\n";
                break;
            case 2:
                LastBinarySearch(0, n, temp, pos);
                fout << pos << "\n";
                break;
        }
    }
    return 0;
}