#include <bits/stdc++.h>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n, k;
int main()
{
    f >> n;
    long long v[n + 1];
    for (int i = 1; i <= n; i++)
        f >> v[i];
    f >> k;
    for (long long x, t; k; k--)
    {
        f >> t >> x;
        if (t == 0)
        {
            int st = 1, dr = n, rez = -1;
            while (st <= dr)
            {
                int m = (st + dr) / 2;
                if (v[m] < x)
                    dr = m - 1;
                else if (v[m] > x)
                    st = m + 1;
                else
                    st = m + 1, rez = m;
            }
            g << rez << '\n';
        }
        else if (t == 1)
        {
            int st = 1, dr = n, rez;
            while (st <= dr)
            {
                int m = (st + dr) / 2;
                if (v[m] <= x)
                    rez = m, st = m + 1;
                else
                    dr = m - 1;
            }
            g << rez << '\n';
        }
        else
        {
            int st = 1, dr = n, rez;
            while (st <= dr)
            {
                int m = (st + dr) / 2;
                if (v[m] >= x)
                    rez = m, dr = m - 1;
                else
                    st = m + 1;
            }
            g << rez << '\n';
        }
    }
    return 0;
}