#include <fstream>
using namespace std;
int v[100000];
int main()
{
    ifstream fin;
    ofstream fout;
    int n, m, t, x, i, st, dr, med;

    fin.open("cautbin.in");
    fout.open("cautbin.out");

    fin>>n;
    for ( i = 0; i < n; i++ ) {
        fin>>v[i];
    }
    fin>>m;
    for ( i = 0; i < m; i++ ) {
        fin>>t>>x;
        if ( t < 2 ) {   // cazurile 0 si 1 sunt similare
        // cautam cea mai mare pozitie pe care se afla <= x in intervalul [0 n)
            st = 0; // capatul din stanga este primul in intervalul [st dr), deci 0
            dr = n; // capatul din dreapta este primul in afara intervalului, deci n
            while ( dr - st > 1 ) {
                med = (dr + st) / 2;
                if ( v[med] > x ) { // element strict mai mare?
                    dr = med; // putem scoate pozitia med in dreapta afara intervalului
                }
                else {
                    st = med; // altfel putem mari limita st catre med
                }
            }
            if ( t == 0 && v[st] != x ) { // in cazul 0 x trebuie sa fie gasit
                st = -2; // vom aduna unu la afisare
            }
        }
        else  {   // cautam prima aparitie a unui numar <= x in intervalul (-1 n-1]
            st = -1; // capatul din stanga este ultimul in afara intervalului (-1 n-1]
            dr = n-1; // capatul din dreapta este ultimul in interval, deci n-1
            while ( dr - st > 1 ) {
                med = (dr + st) / 2;
                if ( v[med] < x ) { // element strict mai mic?
                    st = med; // putem scoate pozitia med in stanga in afara intervalului
                }
                else {
                    dr = med; // altfel putem micsora limita dr catre med
                }
            }
            st = dr; // pentru a afisa totdeauna st ca rezultat
        }
        fout<<st + 1<<endl; // ajustam pozitia cu unu, ca in cerinta
    }

    return 0;
}