#include<fstream.h>
int N, M, v[100005];
int BS1(int x)
{
    int lo, hi, mid;

    for (lo = 1, hi = N; lo <= hi; )
    {
        mid = lo + (hi-lo) / 2;
        if (x < v[mid]) hi = mid-1;
        else if (v[mid] < x) lo = mid+1;
        else return mid;
    }
    return -1;
}

int BS2(int x)
{
    int lo, hi, mid, last = 0;

    for (lo = 1, hi = N; lo <= hi; )
    {
        mid = lo + (hi-lo) / 2;
        if (v[mid] <= x) last = mid, lo = mid+1;
        else hi = mid-1;
    }
    return last;
}

int BS3(int x)
{
    int lo, hi, mid, last = N+1;

    for (lo = 1, hi = N; lo <= hi; )
    {
        mid = lo + (hi-lo) / 2;
        if (x <= v[mid]) last = mid, hi = mid-1;
        else lo = mid+1;
    }
    return last;
}

int main(void)
{
    int i, t, x;

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

    f>>N;
    for (i = 1; i <= N; ++i)
        f>>v[i];

    f>>M;
    for (; M; --M)
    {
        f>>t>>x;
        if (!t)
            g<<BS1(x)<<"\n";
        else if (t == 1)
            g<<BS2(x)<<"\n";
        else
            g<<BS3(x)<<"\n";
    }
}