#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;

int cautbin ( long long x ){
    long long pas = 1 << 16;
    int rez = 0;
    while( pas != 0){
        if( rez + pas <= n && v[rez + pas] <= x)
            rez += pas;
        pas /= 2;
    }
    return rez;
}

int cautbin_ver2 ( long long x){
    long long pas = 1 << 16;
    int rez = 0;
    while( pas != 0){
        if( rez + pas <= n && v[rez+pas] < x)
            rez += pas;
        pas /= 2;
    }
    return rez;
}

int main()
{
    ifstream in ("cautbin.in");
    ofstream out ("cautbin.out");
    int m;
    in >> n;
    for ( int i = 1; 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 << "\n";
                else
                    out << -1 << "\n";
                break;
            }
        case 1:
            {
                int rez = cautbin(x);
                out << rez << "\n";
                break;
            }
        default:
            {
                int rez = cautbin_ver2(x);
                out << rez + 1 << "\n";
            }
        }
    }
    return 0;
}