#include<cstdio>
using namespace std;
int n,i,m,op,x,a[100005];
int cautbin0(int x)
{
    int l=1,r=n,m;
    while(l<=r)
    {
        m=(l+r)/2;
        if(x==a[m]) break;
        if(x<a[m]) {r=m-1;continue;}
        if(x>a[m]) {l=m+1;continue;}
    }
    if(x==a[m])
    {
        while(a[m]==x) m++;
        m--;
        return m;
    }
    return -1;
}
int cautbin1(int x)
{
    int l=1,r=n,m;
    while(l<=r)
    {
        m=(l+r)/2;
        if(x==a[m]) break;
        if(x<a[m]) {r=m-1;continue;}
        if(x>a[m]) {l=m+1;continue;}
    }
    if(x==a[m])
    {
        while(a[m]==x) m++;
        m--;
        return m;
    }
    else {m--;return m;}
}
int cautbin2(int x)
{
    int l=1,r=n,m;
    while(l<=r)
    {
        m=(l+r)/2;
        if(x==a[m]) break;
        if(x<a[m]) {r=m-1;continue;}
        if(x>a[m]) {l=m+1;continue;}
    }
    if(x==a[m])
    {
        while(a[m]==x) m--;
        m++;
        return m;
    }
    else
    {
        m--;
        x=a[m];
        while(a[m]==x) m--;
        m++;
        return m;
    }
}
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(;m;m--)
    {
        scanf("%d%d",&op,&x);
        switch(op)
        {
            case 0:
                printf("%d\n",cautbin0(x));
                break;
            case 1:
                printf("%d\n",cautbin1(x));
                break;
            default:
                printf("%d\n",cautbin2(x));
        }
    }
    return 0;
}