#include <bits/stdc++.h>
#include <cstdlib>
#define ll long long
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define all(a) (a).begin(),(a).end()
using namespace std;
const int maxn = 1e5 + 5;

int bsearch(const vector<int>& a, int x) {
    int l = 0;
    int r = a.size() - 1;
    int pos = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (a[mid] == x) {
            pos = mid;
            l = mid + 1;
        }
        else if (a[mid] < x) {
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }
    return pos + 1;
}

int query1(const vector<int>& a, int x) {
    int l = 0;
    int r = a.size() - 1;
    int pos = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (a[mid] <= x) {
            pos = mid;
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }
    return pos + 1;
}

int query2(const vector<int>& a, int x) {
    int l = 0;
    int r = a.size() - 1;
    int pos = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x) {
            pos = mid;
            r = mid - 1;
        }
        else {
            r = mid - 1;
        }
    }
    return pos + 1;
}

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

void solve() {
    int n;
    fin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        fin >> a[i];
    }
    int q;
    fin >> q;
    while (q--) {
        int type, x;
        fin >> type >> x;
        if (type == 0) {
            fout << bsearch(a, x) << endl;
        }
        else if (type == 1) {
            fout << query1(a, x) << endl;
        }
        else {
            fout << query2(a, x) << endl;
        }
    }
}
 
int main() {
    int t = 1;
    //fin >> t;
    while (t--) {
        solve();
    }
    return 0;
}