#include <iostream>
#include <fstream>
using namespace std;

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

void firstCase(int n, int v[], int x) {
    int left = 1;
    int right = n + 1;
    while (left < right) {
        int middle = (left + right) / 2;
        if (v[middle] <= x) {
            ++left;
        } else {
            right = middle;
        }
    }
    if (v[left - 1] == x) {
        fout << left - 1;
    } else {
        fout << -1;
    }
}

void secondCase(int n, int v[], int x) {
    int left = 1;
    int right = n + 1;
    while (left < right) {
        int middle = (left + right) / 2;
        if (v[middle] <= x) {
            ++left;
        } else {
            right = middle;
        }
    }
    fout << left - 1;
}

void thirdCase(int n, int v[], int x) {
    int left = 1;
    int right = n;
    while (left < right) {
        int middle = (left + right) / 2;
        if (v[middle] < x) {
            ++left;
        } else {
            right = middle;
        }
    }
    fout << left;
}


int main() {
    int n, v[100001];
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> v[i];
    }
    int cases;
    fin >> cases;
    for (int i = 1; i <= cases; ++i) {
        int currentCase, x;
        fin >> currentCase >> x;
        if (currentCase == 0) {
            firstCase(n, v, x);
        } else if (currentCase == 1) {
            secondCase(n, v, x);
        } else {
            thirdCase(n, v, x);
        }
        fout << "\n";
    }
}