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

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

const int N = 100000;
const int L = 16;
int n;
int v[N + 1];

int bin0(int x){
    int r = 0, pas = 1 << L;
    while(pas != 0){
        if(r + pas <= n && v[r + pas] <= x)
            r += pas;
        pas /= 2;
    }
    if(v[r] < x)
        return -1;
    return r;
}

int bin1(int x){
    int r = 0, pas = 1 << L;
    while(pas != 0){
        if(r + pas <= n && v[r + pas] <= x)
            r += pas;
        pas /= 2;
    }
    return r;
}

int bin2(int x){
    int r = 0, pas = 1 << L;
    while(pas != 0){
        if(r + pas <= n && v[r + pas] < x)
            r += pas;
        pas /= 2;
    }
    return r + 1;
}

int main()
{
    int i,k,op,x;
    fin >> n;
    for(i=1; i <= n; i++)
        fin >> v[i];
    fin >> k;
    while(k--){
        fin >> op >> x;
        if(op == 0)
            fout << bin0(x) << "\n";
        else if(op == 1)
            fout << bin1(x) << "\n";
        else
            fout << bin2(x) << "\n";
    }
    return 0;
}