#include<cstdio>
using namespace std;
int a[100000],n,m,k,x,i,poz;
int search0(int k)
{
    int step,i;
    for (step=1;step<n; step<<=1 );
    for (i=0;step;step>>=1)
        if (i+step<n && a[i+step] <= k) i+=step;
    return i;
}
int search1(int k)
{
    int step,i;
    for ( step=1 ; step<=n ; step<<=1 );
    for (i=0; step; step>>=1 )
        if (i+step<n && a[i+step]  <= k) i=step;
    return i;
}
int search2(int k)
{
    int step,i;
    for ( step=1 ; step<=n ; step<<=1);
    for (i=n;step;step >>= 1)
        if (i-step>0 && a[i-step] >= k) i-=step;
    return i;
}
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",&k,&x);

        if (k==0) poz=search0(x);
        if (k==1) poz=search1(x);
        if (k==2) poz=search2(x);
        if (poz==0)poz=-1;
        printf("%d\n",poz);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}