#include <iostream>
#include <fstream>

using namespace std;

int n, a[100002], m, q, x;
ifstream in("cautbin.in");
ofstream out("cautbin.out");

int bs1(int l, int r, int x){
    int mid;
    while(l <= r){
        mid = l + (r - l) / 2;
        if(a[mid] == x){
            if(mid == r or a[mid + 1] > x) return mid;
            else l = mid + 1;
        }
        else {
            if(a[mid] > x) r = mid - 1;
            else l = mid + 1;
        }
    }
    return -1;
}

int bs2(int l, int r, int x){//cea mai mare pozitie pe care se afla un element cu valoarea <= x
    int mid;
    while(l <= r){
        mid = l + (r - l) / 2;
        if(a[mid] <= x){
            if(mid == r or a[mid + 1] > x)
                return mid;
            else
                l = mid + 1;
        }
        else
            r = mid - 1;
    }
    return mid;
}

int bs3(int l, int r, int x){// cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir
    int mid;
    while(l <= r){
        mid = l + (r - l) / 2;
        if(a[mid] >= x){
            if(mid == l or a[mid - 1] < x) return mid;
            else r = mid - 1;
        }
        else l = mid + 1;
    }
    return mid;
}

int main()
{
    in >> n;
    for(int i = 1; i <= n; i++) in >> a[i];

    in >> m;
    for(int i = 1; i <= m; i++){
        in >> q >> x;
        if(q == 0) out << bs1(1, n, x) << "\n";
        if(q == 1) out << bs2(1, n, x) << "\n";
        if(q == 2) out << bs3(1, n, x) << "\n";
    }
    return 0;
}