#include <bits/stdc++.h>
using namespace std;

int32_t main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    int n; cin >> n;
    vector<int> v(n);
    for (auto &it : v) cin >> it;
    int m; cin >> m;
    while (m--) {
        int x, q; cin >> q >> x;
        if (q == 0) {
            cout << (binary_search(v.begin(), v.end(), x) ? upper_bound(v.begin(), v.end(), x) - v.begin() : -1) << '\n';
        } else if (q == 1) {    
            cout << (binary_search(v.begin(), v.end(), x) ? upper_bound(v.begin(), v.end(), x) : lower_bound(v.begin(), v.end(), x)) - v.begin() << '\n'; 
        } else {
            cout << lower_bound(v.begin(), v.end(), x) - v.begin() + 1 << '\n';
        }
    }
    return 0;
}