#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
#include <unordered_map>
#include <stack>
#include <iomanip>
#include <random>
#include <climits>

using namespace std;

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

const int MAX = 1e5 + 1;

int v[MAX];

int binarySearch1(int element, int maxRight) {
    int left = 0;
    int right = maxRight - 1;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (v[mid] == element) {
            while (mid < maxRight && v[mid] == element) {
                ++mid;
            }
            return mid - 1;
        }
        if (v[mid] < element) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

int binarySearch2(int element, int maxRight) {
    int left = 0;
    int right = maxRight - 1;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (v[mid] <= element) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return left - 1;
}

int binarySearch3(int element, int maxRight) {
    int left = 0;
    int right = maxRight - 1;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (v[mid] < element) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return left;
}

int main() {
    int n, m;
    fin >> n;

    for (int i = 0; i < n; ++i) {
        fin >> v[i];
    }

    fin >> m;

    for (int i = 0; i < m; ++i) {
        int type, number;
        fin >> type >> number;

        if (type == 0) {
            int position = binarySearch1(number, n);
            fout << (position == -1 ? -1 : position + 1) << "\n";
        } else if (type == 1) {
            int position = binarySearch2(number, n);
            fout << (position == -1 ? -1 : position + 1) << "\n";
        } else if (type == 2) {
            fout << binarySearch3(number, n) + 1 << "\n";
        }
    }

    return 0;
}