#pragma region Template
#include <bits/stdc++.h>
using namespace std;
#define ll long long

// Files
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
#pragma endregion Template

int binSrc(vector<ll> vect, ll find) {
    int left = 0, right = vect.size() - 1;
    int pos = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (vect[mid] == find)
            pos = mid + 1, left = mid + 1;
        else if (vect[mid] < find)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return pos;
}

int lowerBound(vector<ll> vect, ll find) {
    int left = 0, right = vect.size() - 1;
    int pos = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (vect[mid] >= find)
            pos = mid + 1, right = mid - 1;
        else if (vect[mid] < find)
            left = mid + 1;
    }
    return pos;
}

int upperBound(vector<ll> vect, ll find) {
    int left = 0, right = vect.size() - 1;
    int pos = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (vect[mid] <= find)
            pos = mid + 1, left = mid + 1;
        else if (vect[mid] > find)
            right = mid - 1;
    }
    return pos;
}


void solve() {
    int n;      fin >> n;
    vector<ll> vect(n);
    for (auto& it : vect)
        fin >> it;
    int m;     fin >> m;
    while (m--) {
        int option, num;     fin >> option >> num;
        int ans;
        switch (option) {
            case 0:
                ans = binSrc(vect, num);
                break;
            case 1:
                ans = upperBound(vect, num);
                break;
            default:
                ans = lowerBound(vect, num);
                break;
        };
        fout << ans << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;  //cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}