#include <fstream>
#include <utility>

using namespace std;

const int N = 100000;

int v[N], n;

int caut_0(int x){
    int st = 0, dr = n - 1, rez = -1;
    while(st <= dr)
    {
        int m = (st + dr) / 2;
        if(v[m] <= x){
            rez = m;
            st = m + 1;
        }else{
            dr = m - 1;
        }
    }
    if(rez == -1 || v[rez] < x)
        return -1;
    return rez + 1;
}

int caut_1(int x){
    int st = 0, dr = n - 1, rez = -1;
    while(st <= dr)
    {
        int m = (st + dr) / 2;
        if(v[m] <= x){
            rez = m;
            st = m + 1;
        }else{
            dr = m - 1;
        }
    }
    return rez + 1;
}

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

int main()
{
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");

    in >> n;
    for(int i = 0; i < n; i++)
        in >> v[i];

    int m, tip, val;
    in >> m;
    for(int i = 0; i < m; i++)
    {
        in >> tip >> val;
        if(tip == 0) out << caut_0(val) << '\n';
        if(tip == 1) out << caut_1(val) << '\n';
        if(tip == 2) out << caut_2(val) << '\n';
    }
    in.close();
    out.close();
    return 0;
}