#include<fstream>
using namespace std;

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

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

int BinSearch0(int Value)
{
    int Sol = -1;
    int Left = 1, Right = N;

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

int BinSearch1(int Value)
{
    int Sol = -1;
    int Left = 1, Right = N;

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

int BinSearch2(int Value)
{
    int Sol = -1;
    int Left = 1, Right = N;

    while(Left<=Right)
    {
        int Mid = (Left + Right) / 2;
        if(A[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>>A[i];
    fin>>M;
    while(M--)
    {
        int op,v;
        fin>>op>>v;
        if(op == 0)
            fout<<BinSearch0(v)<<"\n";
        if(op == 1)
            fout<<BinSearch1(v)<<"\n";
        if(op == 2)
            fout<<BinSearch2(v)<<"\n";
    }
    return 0;
}