#include <cstdio>

using namespace std;
int n,m,a[100010],nr,x;
void rule1()
{
    int st=1,dr=n,mid;
    while(st<=dr)
    {
         mid=(st+dr)/2;
        if(a[mid]==x)
            break;
        else if(a[mid]<x)
        {
            st=mid+1;
        }
        else
            dr=mid-1;
    }
    if(st>dr)
        printf("-1\n");
    else
    {
        while(a[mid]==x)
                mid++;
        printf("%d\n",mid-1);
    }
}
void rule2()
{
    int st=1,dr=n,mid=(st+dr)/2;
    while(st<dr)
    {
        if(a[mid]==x)
            break;
        else if(a[mid]<x)
            st=mid+1;
        else
            dr=mid-1;
        mid=(st+dr)/2;
    }
    if(st>=dr)
    {
        if(a[mid]>x)
            printf("%d\n",mid-1);
        else
            printf("%d\n",mid);
    }
    else
        while(a[mid]==x)
                mid++;
        printf("%d\n",mid-1);
}
void rule3()
{
    int st=1,dr=n,mid;
    while(st<dr)
    {
        mid=(st+dr)/2;
        if(a[mid]==x)
            break;
        else if(a[mid]<x)
            st=mid+1;
        else
            dr=mid-1;
    }
    if(st>=dr)
    {
        if(a[mid]<x)
            printf("%d\n",mid+1);
        else
            printf("%d\n",mid);
    }
    else
        while(a[mid]>=x)
            mid--;
    printf("%d\n",mid+1);
}
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=0;i<m;i++)
    {
        scanf("%d %d",&nr,&x);
        if(nr==0)
            rule1();
        else if(nr==1)
            rule2();
        else
            rule3();
    }
    return 0;
}