#include<cstdio>

using namespace std;

int n,a[100004],x,fel,m,i;

int caut0(int x)
{
    int st,dr,mij;
    st=1;
    dr=n;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]==x&&a[mij+1]!=x)
        {
            return mij;
        }
        else
        {
            if(a[mij]==x)
            {
                st=mij+1;
            }
            else
            {
                if(a[mij]<x)
                {
                    st=mij+1;
                }
                else dr=mij-1;
            }
        }
    }
    return -1;
}

int caut1(int x)
{
    int st,dr,mij;
    st=1;
    dr=n;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]<=x&&a[mij+1]>x)
        {
            return mij;
        }
        else
        {
            if(a[mij]<=x)
            {
                st=mij+1;
            }
            else
            {
                if(a[mij]<x)
                {
                    st=mij+1;
                }
                else dr=mij-1;
            }
        }
    }
}

int caut2(int x)
{
    int st,dr,mij;
    st=1;
    dr=n;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]>=x&&a[mij-1]<x)
        {
            return mij;
        }
        else
        {
            if(a[mij]>=x)
            {
                dr=mij-1;
            }
            else
                if(a[mij]<x)
                {
                    st=mij+1;
                }
                else dr=mij-1;
        }
    }
}

int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&fel,&x);
        if(fel==0)
        {
            printf("%d\n",caut0(x));
        }
        if(fel==1)
        {
            if(caut0(x)==-1)
                printf("%d\n",caut1(x));
            else printf("%d\n",caut0(x));
        }
        if(fel==2)
        {
            if(caut0(x)==n)
            {
                printf("%d\n",n);
            }
            else
                printf("%d\n",caut2(x));
        }
    }
    return 0;
}