#include <bits/stdc++.h>
#include <fstream>

using namespace std;

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

long long v[100005];

int main()
{
    long long n, m, i, j, x, st, dr, mid, c, tip;

    cin >> n;

    for (i = 1; i <= n; i++)
    {
        cin >> v[i];
    }

    cin >> m;

    for (i = 0; i < m; i++)
    {
        cin >> tip >> x;

        if (tip == 0)
        {
            st = 1;
            dr = n;
            c = -1;

            while (st <= dr)
            {
                mid = st + (dr - st) / 2;

                if (v[mid] == x)
                {
                    c = mid;
                    st = mid + 1;
                }
                else if (v[mid] < x)
                {
                    st = mid + 1;
                }
                else
                {
                    dr = mid - 1;
                }
            }
            cout << c << "\n";
        }
        else
        if (tip == 1)
        {
            st = 1;
            dr = n;
            c = -1;

            while (st <= dr)
            {
                mid = st + (dr - st) / 2;

                if (v[mid] <= x)
                {
                    c = mid;
                    st = mid + 1;
                }
                else
                {
                    dr = mid - 1;
                }
            }
            cout << c << "\n";
        }
        else
        if (tip == 2)
        {
            st = 1;
            dr = n;
            c = -1;

            while (st <= dr)
            {
                mid = st + (dr - st) / 2;

                if (v[mid] >= x)
                {
                    c = mid;
                    dr = mid - 1;
                }
                else
                {
                    st = mid + 1;
                }
            }
            cout << c << "\n";
        }
    }

    return 0;
}