#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

const int N = 100001;
int v[N], n;

int cautbin ( int x ){
    int rez = 0, pas = 1 << 17;
    while( pas != 0){
        if( rez + pas < n && v[rez+pas] <= x)
            rez += pas;
        pas = pas >> 1;
    }
    return rez;
}

int cautbin_ver2 ( int x){
        int rez = 0, pas = 1 << 17;
    while( pas != 0){
        if( rez + pas < n && v[rez+pas] < x)
            rez += pas;
        pas = pas >> 1;
    }
    return rez;
}

int main()
{
    ifstream in ("file.in");
    ofstream out ("file.out");
    int m;
    in >> n;
    for ( int i = 0; i < n; i++)
        in >> v[i];
    in >> m;
    while( m != 0 ){
        int q, x;
        in >> q >> x;
        m--;
        switch (q){
        case 0:
            {
                int rez = cautbin(x);
                if ( v[rez] == x)
                    out << rez + 1 << "\n";
                else
                    out << "-1\n";
                break;
            }
        case 1:
            {
                int rez = cautbin(x);
                out << rez + 1 << "\n";
                break;
            }
        default:
            {
                int rez = cautbin_ver2(x);
                out << rez + 2 << "\n";
            }
        }
    }
    return 0;
}