#include <fstream>
#include <algorithm>
#include <iostream>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

const int DMAX = 100005;
int v[DMAX], n;

int cautBin0(int val){
    int p = 1 << 17;
    int sol = 0;
    while (p > 0){   
        if (sol + p <= n && v[sol + p] <= val){
            sol += p;
        }
        p = p >> 1;
    }
    if (v[sol] == val){
        return sol;
    } 
    return -1;
}

int cautBin1(int val){
    int p = 1 << 17;
    int sol = 0;
    while (p > 0){   
        if (sol + p <= n && v[sol + p] <= val){
            sol += p;
        }
        p = p >> 1;
    }
    return sol;
}

int cautBin2(int val){
    int p = 1 << 17;
    int sol = 0;
    while (p > 0){   
        if (sol + p <= n && v[sol + p] < val){
            sol += p;
        }
        p = p >> 1;
    }
    sol++;
    return sol;
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++){
        fin >> v[i];
    }
    int k, c, val;
    fin >> k;
    for (int i = 0; i < k; i++) {
        fin >> c >> val;
        if (c == 0) {
            fout << cautBin0(val) << "\n";
        }
        else if (c == 1){
            fout << cautBin1(val) << "\n";
        }
        else {
            fout << cautBin2(val) << "\n";
        }
        
    }
    
    
    return 0;
}