#include <fstream>
using namespace std;

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

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

void Read()
{
    fin>>N;
    for(int i = 1; i <= N; ++i)
        fin>>X[i];
}

int Cbin0(int Val)
{
    int Left = 1, Right = N, Sol = -1;
    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 Left = 1, Right = N, Sol = -1;
    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 Left = 1, Right = N, Sol = -1;
    while(Left <= Right)
        {
            int Mid = (Left + Right) / 2;
            if(X[Mid] >= Val)
                {
                    Sol = Mid;
                    Right = Mid - 1;
                }
            else
                {
                    Left = Mid + 1;
                }
        }
    return Sol;
}

void SolveandPrint()
{
    fin>>M;
    while(M--)
    {
        int op,x;
        fin>>op>>x;
        if(op == 0)
            fout<<Cbin0(x)<<"\n";
        if(op == 1)
            fout<<Cbin1(x)<<"\n";
        if(op == 2)
            fout<<Cbin2(x)<<"\n";
    }
}

int main()
{
    Read();
    SolveandPrint();
    return 0;
}