#include <bits/stdc++.h>
std::ifstream fin("cautbin.in");
std::ofstream fout("cautbin.out");

int n, m, v[100001];

int cautBin0(int v[], int x)
{
    int st = 0, dr = n - 1, mij, rasp = -1;
    while(st <= dr)
    {
        mij = st + (dr - st) / 2;
        if(v[mij] <= x)
        {   st = mij + 1;
            if(v[mij] == x)
                rasp = std::max(mij, rasp);
        }
        else
            dr = mij - 1;
    }
    if(rasp != -1)
        return rasp + 1;
    return rasp;
}

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

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

int main()
{
    int op, x, i;
    fin >> n;
    for(i = 0; i < n; i ++)
        fin >> v[i];
    fin >> m;
    for(i = 0; i < m; i ++)
    {
        fin >> op >> x;
        if(op == 0)
            fout << cautBin0(v, x) << '\n';
        else if(op == 1)
            fout << cautBin1(v, x) << '\n';
        else
            fout << cautBin2(v, x) << '\n';
    }

    return 0;
}