#include <fstream>
#include <iostream>
#define DM 100005
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[DM], n, val, x, q, pos;

int best_cautbin(int x)
{
    int st = 0, dr = n + 1, mij;
    while (dr - st > 1)
    {
        mij = (st + dr) / 2;
        if(x < v[mij])
            dr = mij;
        else
            st = mij;
    }
    if(v[st] != x || st == 0)
        return -1;
    return st;
}
int cautbin_biti(int x)
{
    int pos = 1, step = 1;
    for(; step <= n; step <<= 1) ;
    for(; step > 0; step >>= 1)
        if(step + pos <= n)
            if(v[step + pos] <= x)
                pos += step;
    if(v[pos] == x)
        return pos;
    else return -1;
}

int cautbin1(int x) // returneaza cea mai mare pozitie pe care se afla un element <= cu x (cea mai din dreapta)
{
    int st = 0, dr = n + 1, mij;
    while (dr - st > 1)
    {
        mij = (st + dr) / 2;
        if(x < v[mij])
            dr = mij;
        else
            st = mij;
    }
    return st;
}

int cautbin2(int x) // returneaza cea mai mica pozitie pe care se afla un element >= cu x (cea mai din stanga)
{
    int st = 0, dr = n + 1, mij;
    while (dr - st > 1)
    {
        mij = (st + dr) / 2;
        if(x <= v[mij]) /// diferenta aici
            dr = mij;
        else
            st = mij;
    }
    return dr;
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> v[i];
    fin >> q;
    for (int i = 1; i <= q; i++)
    {
        fin >> val >> x;
        //if(val == 0) fout << best_cautbin(x);
        if(val == 0) fout << cautbin_biti(x);
        if(val == 1) fout << cautbin1(x);
        if(val == 2) fout << cautbin2(x);
        fout << '\n';

    }
    return 0;
}