#include <bits/stdc++.h>
using namespace std;

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

int v[100000001];
int n, m, a, b, cer, x;

void citire(){
    fin >> n;
    for(int i = 1; i <= n; ++i) cin >> v[i];

    fin >> m;
}

int rez0(){
    int poz = 0;

    for(int p = pow(2, 30); p > 0; p>>=1){
        if(poz + p <= x && v[poz + p] <= x){
            poz += p;
        }
    }
    if(v[poz] != x) return -1;
    while(v[poz + 1] == x) poz++;

    return poz;
}

int rez1(){
    int poz = 0;

    for(int p = pow(2, 30); p > 0; p>>=1){
        if(poz + p <= x && v[poz + p] <= x){
            poz += p;
        }
    }
    while(v[poz + 1] <= x) poz++;

    return poz;
}

int rez2(){
    int poz = 0;

    for(int p = pow(2, 30); p > 0; p>>=1){
        if(poz + p <= x && v[poz + p] <= x){
            poz += p;
        }
    }
    while(v[poz - 1] >= x) poz--;

    return poz;
}

int main()
{
    citire();

    for(int i = 1; i <= m; ++i){
        fin >> cer >> x;
        if(cer == 0){
            fout << rez0() << '\n';
        }
        else if(cer == 1){
            fout << rez1() << '\n';
        }
        else {
            fout << rez2() << '\n';
        }
    }
}