#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ("cautbin.in");
ofstream cout ("cautbin.out");
int n, i, a[100001], m, test, x, p;
int main ()
{
    cin >> n;
    for (i=1; i<=n; i++)
        cin >> a[i];
    cin >> m;
    for (i=1; i<=m; i++){
        cin >> test >> x;
        if (test==0){
            p = upper_bound(a+1, a+n+1, x)-a;
            p--;
            if (a[p]!=x) cout << 0 << '\n';
            else cout << p << '\n';
        }
        else if (test==1){
            p = upper_bound(a+1, a+n+1, x) - a;
            if (p>0) p--;
            cout << p<< '\n';
        }
        else {
            p = lower_bound(a+1, a+n+1, x)-a;
            cout << p << '\n';
        }
    }
    return 0;
}