#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 100005;
vector <int> v;
int n, m;

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

int bs0(int x) {
    int last = -1, st = 0, dr = n - 1, med;
    while(st <= dr){
        med = (st + dr) / 2;
        if(v[med] < x) {
            st = med + 1;
        }
        else if(v[med] > x) {
            dr = med - 1;
        }
        else {
            last = med + 1;
            st = med + 1;
        }
    }
    return last;
}

int bs1(int x) {
    int last = -1, st = 0, dr = n - 1, med;
    while(st <= dr){
        med = (st + dr) / 2;
        if(v[med] <= x) {
            last = med;
            st = med + 1;
        }
        else if(v[med] > x) {
            dr = med - 1;
        }
    }
    return last + 1;
}

int bs2(int x) {
    int last = NMAX + 5, st = 0, dr = n - 1, med;
    while(st <= dr){
        med = (st + dr) / 2;
        if(v[med] < x) {
            st = med + 1;
        }
        else if(v[med] >= x) {
            last = med;
            dr = med - 1;
        }
    }
    return last + 1;
}

int main()
{
    int x, i, y;
    fin >> n;
    for(i = 0; i < n; i++) {
        fin >> x;
        v.push_back(x);
    }
    fin >> m;
    for(i = 1; i <= m; i++) {
        fin >> x >> y;
        if(x == 0){
            fout << bs0(y) << "\n";
        }
        else if(x == 1){
            fout << bs1(y) << "\n";
        }
        else {
            fout << bs2(y) << "\n";
        }
    }
    return 0;
}