#include <iostream>
#include <fstream>

unsigned int n, m, v[int(1e5)+1], c, x;

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

int cautbin0(unsigned int x){
    unsigned int step, i;

    for(step = 1; step <= n; step = (step << 1));

    for(i = 0; step; step = (step >> 1))
        if(i + step < n && v[i + step] <= x) i += step;


    if(v[i] == x) return i;

    return -1;
}

int cautbin1(unsigned int x){
    unsigned int step, i;

    for(step = 1; step < n; step = (step << 1));

    for(i = 0; step; step = (step >> 1))
        if(i + step < n && v[i + step] <= x) i += step;


    return i;
}

int cautbin2(unsigned int x){
     int step, i;

    for(step = 1; step < n; step = (step << 1));

    for(i = n; step; step = (step >> 1))
        if(i - step > 0 && v[i - step] >= x) i -= step;



    return i;

}

int main()
{
    fin >> n;

    for(unsigned i = 1; i <= n; i++) fin >> v[i];

    fin >> m;

    for(; m; m--){
        fin >> c >> x;

        if(c == 0) fout << cautbin0(x);
        else if(c==1) fout << cautbin1(x);
        else fout << cautbin2(x);

        fout << "\n";
    }
}