#include <bits/stdc++.h>
using namespace std;

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

int n, m;
int v[100005];

int main()
{
    f >> n;
    for (int i = 0; i < n; i++)
    {
        f >> v[i];
    }
    int m;
    f >> m;
    for (int i = 1; i <= m; i++)
    {
        int q, nr;
        f >> q >> nr;
        if (q == 0)
        {
            int poz = upper_bound(v, v+n, nr) - v - 1;
            if (v[poz] == nr)
            {
                g << poz+1  << '\n';
            }
            else {
                g << -1 << '\n';
            }
        }
        else if (q == 1)
        {
            int poz = upper_bound(v, v + n, nr) - v - 1;
            g << poz + 1 << '\n';
        }
        else {
            int poz = lower_bound(v, v + n, nr) - v;
            g << poz + 1 << '\n';
        }
    }
    return 0;
}