#include <iostream>
#include <fstream>

using namespace std;

int v[100010],N,M;

int CB0(int st, int dr, int x)
{
    int mij;
    if(st>dr)
        return -1;
    else
    {
        mij=st+(dr-st)/2;
       if(v[mij]==x)
        if(v[mij+1]==x && mij!=N)
                return CB0(mij+1,dr,x);
        else
                return mij;
        if(x>v[mij])
            return CB0(mij+1,dr,x);
        else
            return CB0(st,mij-1,x);

    }

}

int CB1(int st, int dr, int x)
{

    int mij;
    if(st>dr) return -1;

    else
    {
        mij=st+(dr-st)/2;
       if(x>=v[mij])
        if(x>=v[mij+1] && mij!=N)return CB1(mij+1,dr,x);
                else
            return mij;
       else
        return CB1(st,mij-1,x);
    }


}

int CB2(int st,int dr,int x)
{

    int mij;
    if(st>dr) return -1;
    else
    {
        mij=st+(dr-st)/2;
        if(x<=v[mij])
            if(x<=v[mij-1] && mij!=1) return CB2(st,mij-1,x);
                else
                    return mij;
        else
            return CB2(mij+1,dr,x);
    }

}

int main()
{
    ifstream f("cautbin.in");
    ofstream g ("cautbin.out");
    int op,val;
    f>>N;
    for (int i=1;i<=N;i++) f>>v[i];
    f>>M;
    for(int i=0;i<M;i++)
    {
        f>>op>>val;
        if(op==0)
                g<<CB0(1,N,val)<<'\n';
        else
            if(op==1)
                g<<CB1(1,N,val)<<'\n';
        else
            g<<CB2(1,N,val)<<'\n';
    }

    return 0;
}