#include <fstream>
#define NMax 100005
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int V[NMax],N,M;

int Cbin0(int x)
{
    int Sol=-1,Left=1,Right=N;
    while(Left<=Right)
        {
            int Mid=(Left+Right)>>1;
            if(V[Mid]==x)
                {
                Sol=Mid;
                Left=Mid+1;
                }
            if(V[Mid]>x)
                Right=Mid-1;
            if(V[Mid]<x)
                Left=Mid+1;
        }
    return Sol;
}
int Cbin1(int x)
{
int Sol,Left=1,Right=N;
    while(Left<=Right)
        {
            int Mid=(Left+Right)>>1;
            if(V[Mid]<=x)
                {
                Sol=Mid;
                Left=Mid+1;
                }
            if(V[Mid]>x)
                Right=Mid-1;

        }
    return Sol;
}
int Cbin2(int x)
{
int Sol=-1,Left=1,Right=N;
    while(Left<=Right)
        {
            int Mid=(Left+Right)>>1;
            if(V[Mid]>=x)
                {
                Sol=Mid;
                Right=Mid-1;
                }
            if(V[Mid]<x)
                Left=Mid+1;
        }
    return Sol;
}

int main()
{
    fin>>N;
    for(int i=1;i<=N;i++)
        fin>>V[i];
    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";

    }

    return 0;
}