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

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;
    }
    if(v[r] < x)
        return -1;
    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;
    }
    if(v[r + 1] == x)
        return r + 1;
    return r;
}

int bin3(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)
        r++;
    return r;
}

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 == 1)
            fout << bin1(x) << "\n";
        else if(op == 2)
            fout << bin2(x) << "\n";
        else
            fout << bin3(x) << "\n";
    }
    return 0;
}