#include <bits/stdc++.h>
#define hlo ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
#define bye fin.close(); fout.close(); return 0;
#define PI acos(-1)
using namespace std;
typedef long long int ll;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
const int VMAX = 100005;
int n, m;
vector < int > v(VMAX);
int cautbinar(int intr, int x)
{
    int s = 1, d = n, m, rez;
    if (intr != 2)
    {
        while (s <= d)
        {
            m = s + (d - s) / 2;
            if (v[m] <= x)
            {
                rez = m;
                s = m + 1;
            }
            else d = m - 1;
        }
        if (!intr)
        {
            if (v[rez] != x)
                return -1;
            return rez;
        }
        if (intr == 1)
        {
            return rez;
        }
    }
    while (s <= d)
    {
        m = s + (d - s) / 2;
        if (v[m] < x)
            s = m + 1;
        else
        {
            rez = m;
            d = m - 1;
        }
    }
    return rez;
}
int main() {
    hlo
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
    fin >> m;
    for (int t = 1; t <= m; ++t)
    {
        int intr, x;
        fin >> intr >> x;
        fout << cautbinar(intr, x) << "\n";
    }
    bye
}