#include <bits/stdc++.h>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n, a[100005], m;
int main()
{
    int i, op, x, p;
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> a[i];
    fin >> m;
    while (m--)
    {
        fin >> op >> x;
        switch (op)
        {
        case 0: 
        {
            p = upper_bound(a + 1, a + n + 1, x) - a;
            if (a[p - 1] == x and p)
                fout << p - 1 << "\n";
            else
                fout << "-1\n";
            break; 
        }
        case 1: 
        {   
            p = upper_bound(a + 1, a + n + 1, x) - a;
            p--;
            if (a[p] == x)
                fout << p << "\n";
            else 
                fout << p - 1 << "\n";
            break; 
        }
        case 2: 
        {   
            p = lower_bound(a + 1, a + n + 1, x) - a;
            if (a[p] == x)
                fout << p << "\n";
            else
                fout << p + 1 << "\n";
            break; 
        }
        }
    }


    return 0;
}