#include <cstdio>

using namespace std;
long n,a[100010],i,m,x,y,j;
//
long caut0(long y)
    {
    long s=1, d=n, lf=-1, mij;
    do{
    mij=(s+d)/2;
    if (a[mij]==y)
        if (lf<mij)
            lf=mij;
    if (a[mij]<=y) s=mij+1;
            else   d=mij-1;
    }while (s<=d);
    return lf;
    }
//
long caut1(long y)
    {
    long s=1, d=n, lf=-1, mij;
    do{
    mij=(s+d)/2;
    if (a[mij]<=y)
        if (lf<mij)
            lf=mij;
    if (a[mij]<=y) s=mij+1;
            else   d=mij-1;
    }while (s<=d);
    return lf;
    }
//
long caut2(long y)
    {
    long s=1, d=n, lf=n+1, mij;
    do{
    mij=(s+d)/2;
    if (a[mij]>=y)
        if (lf>mij)
            lf=mij;
    if (a[mij]>=y) d=mij-1;
            else   s=mij+1;
    }while (s<=d);
    return lf;
    }
//
int main()
{
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);
scanf("%ld",&n);
for (i=1; i<=n; i++)
    scanf("%ld",&a[i]);
scanf("%ld",&m);
for (i=1; i<=m; i++)
    {
    scanf("%ld%ld",&x,&y);
    if (x==0) j=caut0(y);
    if (x==1) j=caut1(y);
    if (x==2) j=caut2(y);
    printf("%ld\n",j);
    }
return 0;
}