#include <fstream>

using namespace std;

int hi, lo, a, b, mid;
int n, m, v[100001];
int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    f>>n;
    for (int i=1; i<=n; i++)
        f>>v[i];
    f>>m;
    for (int j=1; j<=m; j++)
    {
        f >> a >> b;
        hi = n + 1;
        lo = 0;
        mid = 0;
        bool ok = 0 ;
        if (a == 0)
        {
            while (hi - lo != 1)
            {
                mid = lo + (hi - lo)/2;
                if (v[mid] <= b) lo = mid;
                    else hi = mid;
                if (v[mid] == b) ok = 1;
            }
            mid = lo + (hi - lo)/2;
            if (ok == 1) g << mid << '\n';
                else g << "-1" << '\n';
        }

        if (a == 1)
        {
            while (hi - lo != 1)
            {
                mid = lo + (hi - lo)/2;
                if (v[mid] <= b) lo = mid;
                    else hi = mid;
            }
            mid = lo + (hi - lo)/2;
            g << mid << '\n';
        }

        if (a == 2)
        {
            while (hi - lo != 1)
            {
                mid = lo + (hi - lo)/2;
                if (v[mid] >= b) hi = mid;
                    else lo = mid;
            }
            g << hi << '\n';
        }
    }
    return 0;
}