#include <iostream>
#include <fstream>

using namespace std;

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

int v[100001], n, m, i, Q, x, mid, le, ri, ok, ans;

int main()
{
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> v[i];
    fin >> m;
    for (i = 1; i <= m; i++)
    {
        fin >> Q >> x;
        le = 1;
        ri = n;
        if (Q == 0)
        {
            ok = 0;
            while (le <= ri)
            {
                mid = (le + ri) / 2;
                if (v[mid] == x)
                {
                    ans = mid;
                    le = mid + 1;
                    ok = 1;
                }
                else if (v[mid] > x)
                    ri = mid - 1;
                else
                    le = mid + 1;
            }
            if (ok == 1)
                fout << ans << "\n";
            else
                fout << "-1\n";
        }
        else if (Q == 1)
        {
            while (le <= ri)
            {
                mid = (le + ri) / 2;
                if (v[mid] <= x)
                {
                    ans = mid;
                    le = mid + 1;
                }
                else
                    ri = mid - 1;
            }
            fout << ans << "\n";
        }
        else
        {
            while (le <= ri)
            {
                mid = (le + ri) / 2;
                if (v[mid] >= x)
                {
                    ri = mid - 1;
                    ans = mid;
                }
                else
                    le = mid + 1;
            }
            fout << ans << "\n";
        }
    }
    return 0;
}