#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)
    {
        mij=st+(dr-st)/2;
       if(v[mij]==x)
        {
            if(mij!=N)
                {if(v[mij+1]!=x) return mij;
                    else
                        return CB0(mij+1,dr,x);}
                else
                    return mij;
        }
        else
            if(x<v[mij])return CB0(st,mij-1,x);
                else
                    return CB0(mij+1,dr,x);
    }
    else return -1;
}

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

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

}

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

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

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)<<endl;
        else
            if(op==1)g<<CB1(1,N,val)<<endl;
        else
            g<<CB2(1,N,val)<<endl;}

    return 0;
}