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

const long long N = 100001;
long long v[N];
long long n;

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

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

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