#include <bits/stdc++.h>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int main (){
    int n, v[100001], m, nr,q;
    fin >> n;
    for (int i = 1; i<=n; i++){
        fin >>v[i];
    }
    fin >> m;
    for (int i = 1; i<=m; i++){
        fin >> q >> nr;
        int st = 1, dr = n, mij, poz;
        switch(q){
        case 0:
            poz = -1;
            while (st <= dr){
                mij = (st + dr)/2;
                if (v[mij] == nr){
                    poz = mij;
                    st = mij + 1;
                }
                else if (v[mij] < nr) st = mij + 1;
                else dr = mij - 1;
            }

            break;
        case 1:
            while (st <=dr){
                mij = (st + dr)/2;
               if (nr >= v[mij]){
                st = mij + 1;
                poz = mij;
               }
               else dr = mij - 1;
            }

            break;
        case 2:
            while (st <=dr){
                mij = (st + dr)/2;
                if (nr <= v[mij]){
                    dr = mij - 1;
                    poz = mij;
                }
                else st = mij + 1;
            }

            break;

        }
        fout << poz << endl;
    }


}