#include <cstdio>

using namespace std;
int a[100005],n,m,q,type,x;
void cautarebinarareg1(int y)
{
    int min=1,max=n,mid=0;
    do
    {
        mid=(max+min)/2;
        if(y>a[mid])
            min=mid+1;
        else if(y<a[mid])
            max=mid-1;
        else if(y==a[mid])
            for(int i=mid;;i++)
                if(a[i]!=a[mid])
                {
                    printf("%d\n",i-1);
                    break;
                }
    }
    while((a[mid+1]<=y && a[mid]!=y) || a[mid]==-1);
        //printf("%d\n",a[mid]);
}
void cautarebinarareg2(int y)
{
    int min=1,max=n,mid=0;
    do
    {
        mid=(min+max)/2;
        if(y>a[mid])
            min=mid+1;
        else if(y==a[mid])
        {
            for(int i=mid;;i++)
                if(a[i]!=a[mid])
                {
                    printf("%d\n",i-1);
                    break;
                }
        }
        else if(y>a[mid] && y>a[mid+1])
            printf("%d\n",mid);

    }
    while(y<a[mid] && a[mid+1]<=y || min>max);
    //printf("%d\n",mid);
}
void cautarebinarareg3(int y)
{
    int min=1,max=n,mid=0;
    do
    {
        mid=(min+max)/2;
        if(y>a[mid])
            min=mid+1;
        else if(y==a[mid])
        {
            for(int i=mid;;i--)
                if(a[i]!=a[mid])
                {
                    printf("%d\n",i+1);
                    break;
                }
        }
        else if(y<a[mid]&&y>a[mid-1])
            printf("%d\n",mid);
    }
    while(y>=a[mid] && a[mid-1]>y || min>max);
    //printf("%d\n",mid);
}
void citire()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    scanf("%d",&q);
    for(int i=0;i<q;i++)
    {
        scanf("%d %d",&type,&x);
        if(type==0)
            cautarebinarareg1(x);
        else if(type==1)
            cautarebinarareg2(x);
        else
            cautarebinarareg3(x);
    }
}
int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    citire();
    return 0;
}