#include <iostream>
#include <fstream>

std::ifstream f("cautbin.in");
std::ofstream g("cautbin.out");

int v[100005], n, i, cer, x, t;
int cb0(int elem)
{
    int st = 1, dr = n, mij, p = -1;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(v[mij] == elem)
        {
            p = mij;
            st = mij + 1;
        }
        else if(v[mij] > elem)
            dr = mij - 1;
        else
            st = mij + 1;
    }
    return p;
}

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

int cb2(int elem) // lower_bound
{
    int st = 1, dr = n, mij = 0;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(v[mij] < elem)
            st = mij + 1;
        else
            dr = mij - 1;
    }
    return st;
}
int main()
{
    f >> n;
    for(i = 1; i <= n; ++ i)
    {
        f >> v[i];
    }
    f >> t;
    for(; t; t --)
    {
        f >> cer >> x;
        if(cer == 0)
            g << cb0(x) << "\n";
        else if(cer == 1)
            g << cb1(x) << "\n";
        else
            g << cb2(x) << "\n";
    }
    return 0;
}