#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

const int maxn=100005;

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

int v[maxn];
int n, m;

int type0(int x) // returneaza cea mai mare pozitie unde se alfa el X
{
    int st=1;
    int dr=n;
    int ret = -1;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(v[mij] < x) {
            st = mij + 1;
        }
        else if(x < v[mij]) {
            dr = mij - 1;
        }
        else if(x == v[mij]) {
            ret = mij;
            st = mij + 1;
        }
    }
    return ret;
}

int type1(int x) {
///cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir.
///Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x
    int st = 1;
    int dr = n;
    int ret = -1;
    while(st <= dr) {
        int mij = (st + dr) / 2;
        if(v[mij] <= x) {
            ret = mij;
            st = mij + 1;
        }
        else
            dr = mij - 1;
    }
    return ret;
}

int type2(int x) {
    ///- cea mai mica pozitie pe care se afla un
    /// element cu valoarea mai mare sau egala cu x in
    int st = 1, dr = n;
    int ret = -1;
    while(st <= dr) {
        int mij = (st + dr) / 2;
        if(v[mij] >= x) {
            ret = mij;
            dr = mij - 1;
        }
        else
            st = mij + 1;
    }
    return ret;
}


int main() {
    in>>n;
    for(int i=1;i<=n;i++)
        in>>v[i];
    in >> m;
    for(int i = 1 ; i <= m ; ++ i) {
        int type, x;
        in >> type >> x;
        if(type == 0)
            out << type0(x) << '\n';
        else if(type == 1)
            out << type1(x) << '\n';
        else if(type == 2)
            out << type2(x) << '\n';
    }
    return 0;
}