#include<cstdio>
#define _NM 100010

int A[_NM], nA;

int bsearch(int val)
{
    int left=1,right=nA;
    while (left<=right)
        {
            int mid=(left+right)/2;
            if (A[mid]==val&&A[mid+1]>val) return mid;
            if (val<A[mid]) right=mid-1;
            else left=mid+1;
        }
    return -1;
}
int lowerb(int val)
{
    int left=1,right=nA;
    while (left<=right)
        {
            int mid=(left+right)/2;
            if (A[mid]<=val&&A[mid+1]>val) return mid;
            if (A[mid]>val) right=mid-1;
            else left=mid+1;
        }
}
int upperb(int val)
{
    int left=1,right=nA;
    while (left<=right)
        {
            int mid=(left+right)/2;
            if (A[mid]>=val&&A[mid-1]<val) return mid;
            if (A[mid]<val) left=mid+1;
            else right=mid-1;
        }
}

int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&nA);
    for (int i=1;i<=nA;i++)
        scanf("%d",&A[i]);
    int nCau; scanf("%d",&nCau);
    for (int i=1;i<=nCau;i++)
    {
        int opt,val; scanf("%d%d",&opt,&val);
        switch(opt)
        {
            case 0: printf("%d\n",bsearch(val)); break;
            case 1: printf("%d\n",lowerb(val)); break;
            case 2: printf("%d\n",upperb(val));
        }
    }
}