#include <cstdio>
int v[100005],m,n,i,a,b;

int Bsearch1(int s,int d)
{
     int m,sol=-1;
    while(s<=d)
    {
        m=(s+d)/2;
        if(v[m]<=b)
        {
            if(v[m]==b)
                sol=m;
            s=m+1;
        }
        else
            if(v[m]>b)
                d=m-1;
    }
    return sol;
}

int Bsearch2(int s,int d)
{
    int m,sol=1;
    while(s<=d)
    {
        m=(s+d)/2;
        if(v[m]<=b)
        {
            sol=m;
            s=m+1;
        }
        else
            if(v[m]>=b)
            d=m-1;
    }
    return sol;
}

int Bsearch3(int s,int d)
{
    int m,sol=1;
    while(s<=d)
    {
        m=(s+d)/2;
        if(v[m]>=b)
        {
            sol=m;
            d=m-1;
        }
        else
        if(v[m]<b)
            s=m+1;
    }
    return sol;
}

int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);

    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    scanf("%d",&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d %d",&a,&b);
        if(a==0)
            printf("%d\n",Bsearch1(1,n));
        if(a==1)
            printf("%d\n",Bsearch2(1,n));
        if(a==2)
            printf("%d\n",Bsearch3(1,n));
    }
    return 0;
}