#include <fstream>
using namespace std;

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

const int NMax = 100005;
int N,M,X[NMax];

int Cbin(int Val)
{
    int Sol = -1;

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

int Cbin1(int Val)
{
    int Sol = -1;
    int Left = 1, Right = N;

    while(Left <= Right)
        {
            int Mid = (Left + Right) / 2;
            if(X[Mid] <= Val)
                {
                    Sol = Mid;
                    Left = Mid + 1;
                }
            else
                Right = Mid - 1;
        }
    return Sol;
}

int Cbin2(int Val)
{
    int Sol = -1;
    int Left = 1, Right = N;

    while(Left <= Right)
        {
            int Mid = (Left + Right) / 2;
            if(X[Mid] >= Val)
                {
                    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<< Cbin(x)<<"\n";
        if(op == 1)
            fout<< Cbin1(x)<<"\n";
        if(op == 2)
            fout<< Cbin2(x)<<"\n";
    }

    return 0;
}