#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n, m, c ;
int v[10000] ;
int cer1(int x) {
    int st = 1, dr = n + 1, mij ;
    while(dr - st > 1) {
        mij = (st + dr) / 2 ;
        if(v[mij] <= x) {
            st = mij ;
        }
        else{
            dr = mij ;
        }
    }
    if(st != x) {
        return -1 ;
    }
    else{
        return dr ;
    }
}
int cer2(int x) {
    int st = 1, dr = n + 1, mij ;
    while(dr - st > 1) {
        mij = (st + dr) / 2 ;
        if(v[mij] <= x) {
            st = mij ;
        }
        else{
            dr = mij ;
        }
    }
    return st ;

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

}
int main()
{
    int val ;
    fin >> n ;
    for(int i = 1 ; i <= n ; i++) {
        fin >> v[i] ;
    }
    fin >> m ;
    for(int i = 1 ; i <= m ; i++) {
        fin >> c >> val ;
        if(c == 0) {
            fout << cer2(val) << endl ;
        }
        else if(c == 1) {
            fout << cer2(val) << endl ;
        }
        else if(c == 2) {
            fout << cer3(val) << endl ;
        }
    }
    return 0;
}