#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int v[100001];

int main()
{
    int n;
    fin >> n;

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

    int m;
    fin >> m;

    while(m--)
    {
        int tip, x;
        fin >> tip >> x;

        if(tip == 0)
        {
            int p = upper_bound(v+1, v+n+1, x) - v - 1;

            if(v[p] == x)
                fout << p << "\n";
            else
                fout << -1 << "\n";
        }

        if(tip == 1)
        {
            int p = upper_bound(v+1, v+n+1, x) - v - 1;
            fout << p << "\n";
        }

        if(tip == 2)
        {
            int p = lower_bound(v+1, v+n+1, x) - v;
            fout << p << "\n";
        }
    }

    return 0;
}