#include<stdio.h>

int n,v[100002];

void cautb0(int x)
{
    int s=1,d=n,m,l=-1;
    while(s<=d)
    {
        m=(s+d)/2;
        if(v[m]==x)
        {
            l=m;
            s=m+1;
        }
        else if(v[m]<x)
            s=m+1;
        else
            d=m-1;
    }
    printf("%d\n",l);
}

void cautb1(int x)
{
    int s=1,d=n,m,l=-1;
    while(s<=d)
    {
        m=(s+d)/2;
        if(v[m]<=x)
        {
            l=m;
            s=m+1;
        }
        else
            d=m-1;
    }
    printf("%d\n",l);
}

void cautb2(int x)
{
    int s=1,d=n,m,l=-1;
    while(s<=d)
    {
        m=(s+d)/2;
        if(v[m]>=x)
        {
            l=m;
            d=m-1;
        }
        else
            s=m+1;
    }
    printf("%d\n",l);
}

int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    int m,t,x,i;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%d",&v[i]);
    scanf("%d",&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&t,&x);
        if(t==0)
            cautb0(x);
        else if(t==1)
            cautb1(x);
        else if(t==2)
            cautb2(x);
    }
    return 0;
}