#include <fstream>
#define nmax 100010

using namespace std;

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

int n, m, v[nmax],i, a, x;

int binsearch(int c){
    int st, dr, val = -1, mij;
    st = 1; dr = n;
    while (st <= dr){
        mij = (st + dr)/ 2;
        if (v[mij] <= c){
            val = mij;
            st = mij + 1;
        }
        else
            dr = mij - 1;
    }
    return val;
}

int binsearch2(int c){
    int st, dr, val = -1, mij;
    st =1; dr = n;
    while (st <= dr){
        mij = (st + dr)/ 2;
        if(v[mij]>= c){
            val = mij;
            dr = mij -1;
    }
    else
        st = mij + 1;
    }
}

int main()
{
    fin >> n;
    for (i = 1; i <= n ; i ++)
        fin >> v[i];
    fin >> m;
    for (i = 1; i <= m; i ++){
        fin >> a >> x;
        int poz = binsearch(x);
        if (a == 0)
            if (v[poz] == x)
                fout << poz << endl;
            else
                fout << -1 << endl;
            else if (a == 1)
                fout << poz << endl;
            else
                fout << binsearch2(x) << endl;
    }
    return 0;
}