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

int n, m, a[100001];

int Bin0(int x)
{
    int sol = -1, st, dr, m;
    st = 1; dr = n;
    while (st <= dr)
    {
        m = (st + dr) / 2;
        if (a[m] < x)
            st = m + 1;
        else if (a[m] > x)
            dr = m - 1;
        else
        {
            st = m + 1;
            sol = m;
        }
    }
    return sol;
}

int Bin1(int x)
{
    int sol, st, dr, m;
    st = 1; dr = n;
    while (st <= dr)
    {
        m = (st + dr) / 2;
        if (a[m] <= x)
        {
            sol = m;
            st = m + 1;
        }
        else if (a[m] > x)
            dr = m - 1;
    }
    return sol;
}

int Bin2(int x)
{
    int sol, st, dr, m;
    st = 1; dr = n;
    while (st <= dr)
    {
        m = (st + dr) / 2;
        if (a[m] >= x)
        {
            sol = m;
            dr = m - 1;
        }
        else if (a[m] < x)
            st = m + 1;
    }
    return sol;
}

int main()
{
    int i, t, x;
    fin >> n;
    for (i = 1 ; i <= n ; i++)
        fin >> a[i];
    fin >> m;
    for (i = 1 ; i <= m ; i++)
    {
        fin >> t >> x;
        if (t == 0)
            fout << Bin0(x) << "\n";
        else if (t == 1)
            fout << Bin1(x) << "\n";
        else
            fout << Bin2(x) << "\n";
    }
    return 0;
}