#include <fstream>

using namespace std;

int v[100001], n;

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

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

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

int main()
{
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    fin >> n;
    for(int i = 0; i < n; i++){
        fin >> v[i];
    }

    int t;
    fin >> t;
    while (t > 0){
        int tip, x;
        fin >> tip >> x;
        if (tip == 0)
        {
            fout << cautbin0(x) << endl;
        }
        else if (tip == 1){
            fout << cautbin1(x) <<endl;
        }
        else {
            fout << cautbin2(x)<<endl;
        }
        t--;
    }
    return 0;
}