#include <bits/stdc++.h>
#include <fstream>
#include <iostream>

using namespace std;

int binary_search(const vector<int>& v, int x, int type) {
    int left = 0, right = v.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (type == 0) {
            if (v[mid] == x) {
                left = mid + 1; // Search for the rightmost occurrence
                if (mid == v.size() - 1 || v[mid + 1] != x) {
                    return mid; // Found the rightmost occurrence
                }
            } else if (v[mid] < x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        } else if  (type == 1) {
            // search for right most occurence of the value samller or equal to x
            if (v[mid] <= x) {
                left = mid + 1;
                if (mid == v.size() - 1 || v[mid + 1] > x) {
                    return mid; // Found the rightmost occurrence
                }
            } else if (v[mid] < x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        } else if (type == 2) {
            // search for left most occurence of the value bigger or equal to x
            if (v[mid] >= x) {
                right = mid - 1;
                if (mid == 0 || v[mid - 1] < x) {
                    return mid; // Found the leftmost occurrence
                }
            } else if (v[mid] > x) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
    }
    return -1; // Not found
}

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

    int n, m;
    fin >> n;
        
    vector<int> v(n);

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

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

        int result = binary_search(v, x, type);
        if (result != -1) {
            fout << result + 1 << endl;
        } else {
            fout << result << endl;
        }
    }
    return 0;
}