#include <fstream>
#include <algorithm>
using namespace std;

const string name("cautbin");
ifstream cin(name + ".in");
ofstream cout(name + ".out");

int n, m, a[100001], task, x;

int cb0(){
    int st = 1, dr = n, rez = -1;
    while(st <= dr){
        int mij = (st + dr) / 2;
        if(a[mij] == x)
            rez = max(rez, mij), st = mij + 1;
        else if(a[mij] > x)
            dr = mij - 1;
        else
            st = mij + 1;
    }
    return rez;
}

int cb1(){
    int st = 1, dr = n, rez = 0;
    while(st <= dr){
        int mij = (st + dr) / 2;
        if(a[mij] <= x)
            rez = max(rez, mij), st = mij + 1;
        else
            dr = mij - 1;
    }
    return rez;
}

int cb2(){
    int st = 1, dr = n, rez = n;
    while(st <= dr){
        int mij = (st + dr) / 2;
        if(a[mij] >= x)
            rez = min(rez, mij), dr = mij - 1;
        else
            st = mij + 1;
    }
    return rez;
}

int main(){

    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    cin >> m;
    for(int i = 1; i <= m; ++i){
        cin >> task >> x;
        if(!task)
            cout << cb0();
        else if(task == 1)
            cout << cb1();
        else
            cout << cb2();
        cout << '\n';
    }

    return 0;
}