#include <fstream>


using namespace std;

int N,M,v[100001];
int cautbin0(int x)
{
    int st,dr,mij,best_pos=-1;
    st=1;
    dr=N;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]<x)
            st=mij+1;
        if(v[mij]>x)
            dr=mij-1;
        if(v[mij]==x)
        {
            best_pos=mij;
            st=mij+1;
        }
    }
    return best_pos;
}
int cautbin1(int x)
{
    int st,dr,mij,best_pos;
    st=1;
    dr=N;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]>x)
        {
            dr=mij-1;
        }
        else//v[mij]<=x
        {
            best_pos=mij;
            st=mij+1;
        }
    }
    return best_pos;
}

int cautbin2( int x)
{
    int st,dr,mij,best_pos;
    st=1;
    dr=N;
    while(st<=dr)
    {
        mij=(dr+st)/2;
        if(v[mij]<x)
            st=mij+1;
        else//v[mij]>=x
        {
            best_pos=mij;
            dr=mij-1;
        }


    }
    return best_pos;
}


ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int main()
{
    int i,x;
    fin>>N;
    for(i=1;i<=N;i++)
        fin>>v[i];
    fin>>M;
    for(i=1;i<=M;i++)
    {
        int tip,x;
        fin>>tip>>x;
        if(tip==0)
            fout<<cautbin0(x)<<"\n";
        if(tip==1)
            fout<<cautbin1(x)<<"\n";
        if(tip==2)
            fout<<cautbin2(x)<<"\n";
    }

    fin.close();

    fout.close();

    return 0;
}