#include <iostream>
#include <fstream>
using namespace std;
#define N 100100
long long v[N],t,x,i,n,m;
int bs_0 (long long x){
    int it = n,p = 0;
    for (; it > 0 ; it >>= 1)
        while (p + it < n && v[p + it] <= x)
            p += it;
    if (v[p] != x)
        return -1;
    return p + 1;
}
int bs_1 (long long x){
    int it = n,p = 0;
    for (; it > 0 ; it >>= 1)
        while (p + it < n && v[p + it] <= x)
            p += it;
    return p + 1;
}
int bs_2 (long long x){
    if (v[0] > x)
        return 1;
    int it = n,p = 0;
    for (; it > 0 ; it >>= 1)
        while (p + it < n && v[p + it] < x)
            p += it;
    return p + 2;
}
int main()
{
    ifstream fin ("cautbin.in");
    ofstream fout ("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 == 0)
            fout << bs_0 (x) << '\n';
        if (t == 1)
            fout << bs_1 (x) << '\n';
        if (t == 2)
            fout << bs_2 (x) << '\n';
    }
    return 0;
}