#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int st,dr,ok,v[100001],i,n,m,x,z,cond,mijl;
void cautbin(int w)
{
    st=1;
    dr=n;
    while(st!=dr&&ok==0)
    {
        mijl=(st+dr)/2;
        if(w==v[mijl])
        {
            ok=1;
            while(w==v[mijl])
                mijl++;
        }
        else
            if(w<v[mijl])
                dr=mijl-1;
            else
                st=mijl+1;
    }
    mijl--;
}
void cautbin1(int z)
{
    st=1;
    dr=n;
    while(st!=dr&&ok==0)
    {
        mijl=(st+dr)/2;
        if(z==v[mijl])
        {
            ok=1;
            while(z==v[mijl])
                mijl--;
        }
        else
            if(z<v[mijl])
                dr=mijl-1;
            else
                st=mijl+1;
    }
    mijl++;
}
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;
    for(i=1;i<=m;i++)
    {
        ok=0;
        fin>>cond>>x;
        if(cond==0)
            {
                cautbin(x);
                fout<<mijl<<'\n';
            }
        else
            if(cond==1)
            {
                x++;
            do{x--;}
            while(x>v[n]);
            cautbin(x);
            fout<<mijl<<'\n';
            }
            else
            {
                x--;
                do{x++;}
                while(x<v[1]);
                cautbin1(x);
                fout<<mijl<<'\n';
            }
    }
}