#include <iostream>
#include <fstream>
using namespace std;

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

int v[100001];

int cautare_binara0(int n, int x) {
    int i, m, j;

    i = 1;
    j = n;
    while(i <= j) {
        m = (i + j) / 2;
        if(v[m] <= x){
            i = m + 1;
        } else {
            j = m - 1;
        }
    }
    m = (i + j) / 2;
    if(v[m] > x) {
        m--;
    }
    if(v[m] == x) {
        return m;
    }
    return -1;
}

int cautare_binara1(int n, int x) {
    int i, j, m;
    i = 1;
    j = n;
    while(i < j){
        m = (i + j) / 2;
        if(v[m] <= x){
         i = m + 1;
        } else {
            j = m;
        }
    }
    m = (i + j) / 2;
    if(v[m] > x) {
        m--;
    }
    return m;
}

int cautare_binara2(int n, int x) {
    int i, j, m;
    i = 1;
    j = n;
    while(i < j){
        m = (i + j) / 2;
        if(v[m] < x){
            i = m + 1;
        } else {
            j = m;
        }
    }
    m = (i + j) / 2;
    if(v[m] < x) {
        m++;
    }
    return m;
}

int main()
{
    int i, n, nr, x, m;
    
    in >> n;
    for(i = 1;i <= n;i++){
        in >> v[i];
    }
    in >> m;
    for(i = 1; i <= m; i++) {
        in >> nr >> x;
        if(nr == 0){
            out << cautare_binara0(n, x) << "\n";
        }
        
        else if(nr == 1){
            out << cautare_binara1(n, x) << "\n";
        }
        
         else{
           out << cautare_binara2(n, x) << "\n";
         }
    }
    return 0;
}