#include <bits/stdc++.h>
#define ll unsigned long long
#define in ios_base::sync_with_stdio(0); fin.tie(NULL); fout.tie(NULL);
#define out return 0;
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n, m, i, x, task, v[100000];
int cautbin0(int v[], ll x)
{
    int st = 1, dr = n, sol = -1;
    while (st <= dr)
        {
            int mid = st + (dr - st) / 2;
            if (v[mid] <= x)
            {
                sol = mid;
                st = mid + 1;
            }
            else
                dr = mid - 1;
        }
    return sol;
}
int cautbin2(int v[], ll x)
{
    int st = 1, dr = n, sol = -1;
    while (st <= dr)
        {
            int mid = st + (dr - st) / 2;
            if (v[mid] >= x)
            {
                sol = mid;
                dr = mid - 1;
            }
            else
                st = mid + 1;
        }
    return sol;
}
int main()
{
    in
    fin >> n;

    for (i = 1; i <= n; ++i)
        fin >> v[i];

    fin >> m;
    while (m--)
    {
        fin >> task >> x;
        if (task == 0) fout << cautbin0(v,x) << "\n";
        if (task == 1) fout << cautbin0(v,x) << "\n";
        if (task == 2) fout << cautbin2(v,x) << "\n";
    }
    out
}