#include <fstream>
#include <iostream>
#define DM 100000
using namespace std;

ifstream fi ("cautbin.in");
ofstream fo ("cautbin.out");
int n, m, a, x, v[DM];

void binar0 ()
{
    int hi = n, lo = 1, mid;
    while (hi - lo > 0)
    {
        mid = (lo + hi + 1)/2;
        if (v[mid] > x)
            hi = mid - 1;
        else
            lo = mid;
    }
    if (v[hi] != x)
        fo << -1 << '\n';
    else
        fo << hi << '\n';
}

void binar1 ()
{
    int hi = n, lo = 1, mid;
    while (hi - lo > 0)
    {
        mid = (lo + hi + 1)/2;
        if (v[mid] > x)
            hi = mid - 1;
        else
            lo = mid;
    }
    fo << hi << '\n';
}

void binar2()
{
    int hi = n, lo = 1, mid;
    while (hi - lo > 0)
    {
        mid = (hi + lo)/2;
        if (v[mid] < x)
            lo = mid + 1;
        else
            hi = mid;
    }
    fo << hi;
}

int main ()
{
    fi >> n;
    for (int i = 1; i <= n; ++i)
        fi >> v[i];
    fi >> m;
    for (int k = 0; k < m; ++k)
    {
        fi >> a >> x;
        if (a == 0)
            binar0();
        else if (a == 1)
            binar1();
        else
            binar2();
    }
    return 0;
}