#include <bits/stdc++.h>

using namespace std;

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

int n, m, v[100001], cerinta, x, i, mij, st, dr;
int main()
{
    fin >> n;

    for (i = 1; i <= n; ++i) fin >> v[i];

    fin >> m;

    for (i = 1; i <= m; ++i)      ///1 3 3 3 5
    {                             ///s 2 3 4 d
        fin >> cerinta >> x;
        if (cerinta == 0){
            st = 1;
            dr = n;
            while (st <= dr)
            {
                mij = (st + dr) / 2;
                if (v[mij] > x) dr = mij - 1;
                if (v[mij] < x) st = mij + 1;
                if (v[mij] == x) st = mij + 1;
            }
            mij = (st + dr) / 2;

            if (v[mij] > x) mij --;
            if (v[mij] == x)
                fout << mij << '\n';
            else fout << -1 << '\n';
        }
        if (cerinta == 1){
            st = 1;
            dr = n;

            while (st < dr)
            {
                mij = (st + dr) / 2;
                if (v[mij] < x) st = mij + 1;
                if (v[mij] == x) st = mij + 1;
                if (v[mij] > x) dr = mij;
            }

            mij = (st + dr) / 2;
            if (v[mij] > x)
               -- mij;
            fout << mij << '\n';
        }
        if (cerinta == 2){
            st = 1;
            dr = n;

            while (st < dr) {
                mij = (st + dr) / 2;
                if (v[mij] < x) st = mij + 1;
                else dr = mij;
            }

            mij = (st + dr) / 2;
            if (v[mij] < x)
               ++ mij;
            fout << mij << '\n';
        }
    }

    return 0;
}