#include <fstream>
#include <iostream>
using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int v[100005],li,ls,n,gasit,mij;

int dr(int x)
{
    li=1;
    ls=n;
    gasit=0;
    while(li<=ls && gasit==0)
    {
        mij=(li+ls)/2;
        if(v[mij]==x)
            gasit=1;
        else if(x<v[mij])
            ls=mij-1;
        else
            li=mij+1;
    }
    if(gasit==0)
        return -1;
    if(v[mij-1]==x)
        while(v[mij-1]==x)
            mij--;
    return mij;
}

int st(int x)
{
    li=1;
    ls=n;
    gasit=0;
    while(li<=ls && gasit==0)
    {
        mij=(li+ls)/2;
        if(v[mij]==x)
            gasit=1;
        else if(x<v[mij])
            ls=mij-1;
        else
            li=mij+1;
    }
    if(gasit==0)
        return -1;
    if(v[mij+1]==x)
        while(v[mij+1]==x)
            mij++;
    return mij;
}

int main()
{
    int i,o,q,m,x;
    f>>n;
    for(i=1; i<=n; i++)
        f>>v[i];
    f>>m;
    for(i=1; i<=m; i++)
    {
        f>>o>>x;
        if(o==0)
            g<<st(x)<<'\n';
        if(o==1)
        {
            q=st(x);
            if(q==-1)
            {
                x--;
                q=st(x);
            }
            g<<q<<'\n';
        }
        if(o==2)
        {
            q=dr(x);
            while(q==-1)
            {
                x++;
                q=st(x);
            }
            g<<q<<'\n';
        }
    }
    return 0;
}