#include <cstdio>

using namespace std;

int n,a[100005],m,x,c;

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

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

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

    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&c,&x);
        if(c==0)
            printf("%d\n",c0(n));
        if(c==1)
            printf("%d\n",c1(n));
        if(c==2)
            printf("%d\n",c2(n));


    }

    return 0;
}