#include <fstream>
#define date "cautbin.in"
#define rezultate "cautbin.out"
#define len 100000

using namespace std;

ifstream in(date);
ofstream out(rezultate);

int N, M, v[len];

int binary_search(int val)
{
    int step, i;
    bool gasit = false;
    for(step = 1; step < N; step <<= 1);
    for(i = 0; step; step >>= 1)
        if(i + step < N && v[i + step] == val)
        {
            gasit = true;
            i += step;
        }
    if(gasit)
        return i + 1;
    return -1;
}

int binary_search1(int val)
{
    int step, i;
    for(step = 1; step < N; step <<= 1);
    for(i = 0; step; step >>= 1)
        if(i + step < N && v[i + step] <= val)
            i += step;
    return i + 1;
}

int binary_search2(int val)
{
    int step, i, k;
    for(step = 1; step < N; step <<= 1);
    for(i = 0; step; step >>= 1)
        if(i + step < N && v[i + step] >= val)
            k = i + step;
    return k + 1;
}

int main()
{
    in >> N;
    for(int i = 0; i < N;)
        in >> v[i++];
    in >> M;
    for(int i = 1; i <= M; ++i)
    {
        int task, x;
        in >> task >> x;
        if(!task)
            out << binary_search(x);
        else if(task == 1)
            out << binary_search1(x);
        else
            out << binary_search2(x);
        out << '\n';
    }
    return 0;
}