#include <stdio.h>

int a[100010],m,n,x,y;

int cb0(int b)
{
    int start=1,stop=n,mid=0,rez=-1;
    while(start<stop+1)
    {
        mid=(start+stop)/2;
        if (a[mid]==b)
        {
            rez=mid;
            start=mid+1;
        }
        if(a[mid]<b)
            start=mid+1;
        if (a[mid]>b)
            stop=mid-1;
    }
    return rez;
}

int cb1(int b)
{
    int start=1,stop=n,mid=0,rez=-1;
    while(start<stop+1)
    {
        mid=(start+stop)/2;
        if (a[mid]<=b)
        {
            rez=mid;
            start=mid+1;
        }
        else
            stop=mid-1;
    }
    return rez;
}

int cb2(int b)
{
    int start=1,stop=n,mid=0,rez=-1;
    while(start<stop+1)
    {
        mid=(start+stop)/2;
        if (a[mid]>=b)
        {
            rez=mid;
            stop=mid-1;
        }
        else
            start=mid+1;
    }
    return rez;
}

int main()
{
    int i;
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for(i=1; i<n+1; ++i)
        scanf("%d",&a[i]);
    scanf("%d",&m);
    for(i=1; i<m+1; ++i)
    {
        scanf("%d%d",&x,&y);
        if (x==0)
            printf("%d\n",cb0(y));
        if (x==1)
            printf("%d\n",cb1(y));
        if (x==2)
            printf("%d\n",cb2(y));
    }
    return 0;
}