#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
const int NMax = 100000;
int X[NMax + 5],N,M;
int BinarySearch(int Value)
{
    int Sol = -1;
    int Left = 1, Right = N;
    while(Left <= Right)
    {
        int Mid = (Left + Right) / 2;
        if(X[Mid] == Value)
        {
            Sol = Mid;
            Left = Mid + 1;
        }
        else
            if(X[Mid] < Value)
                Left = Mid + 1;
            else
                Right = Mid - 1;
    }
    return Sol;
}

int BinarySearch1(int Value)
{
    int Sol;
    int Left = 1, Right = N;
    while(Left <= Right)
    {
        int Mid = (Left + Right) / 2;
        if(X[Mid] <= Value)
            {
                Sol = Mid;
                Left = Mid + 1;
            }
            else
                Right = Mid - 1;
    }
    return Sol;
}
int BinarySearch2(int Value)
{
    int Sol;
    int Left = 1, Right = N;
    while(Left <= Right)
    {
        int Mid = (Left + Right) / 2;
        if(X[Mid] >= Value)
            {
                Sol = Mid;
                Right = Mid - 1;
            }
            else
               Left = Mid + 1;
    }
    return Sol;
}


int main()
{
    fin >> N;
    for(int i = 1; i <= N; ++i)
        fin >> X[i];
    fin >> M;
    while(M--)
    {
        int op,x;
        fin >> op >> x;
        if(op == 0)
            fout << BinarySearch(x) << "\n";
        if(op == 1)
            fout << BinarySearch1(x)<<"\n";
        if(op == 2)
            fout << BinarySearch2(x)<<"\n";
    }
    return 0;
}