#include <cstdio>
#define Nmax 100005

using namespace std;

FILE *fin=freopen("cautbin.in","r",stdin);
FILE *fout=freopen("cautbin.out","w",stdout);

int n,a[Nmax],t;

int bin0(int st, int dr, int v)
{
    int mid;
    while(st<=dr)
    {
        mid=(st+dr)>>1;
        if(a[mid]<=v)
            st=mid+1;
        else
            dr=mid-1;
    }
    mid=(st+dr)>>1;
    if(a[mid]>v)
        mid--;
    if(a[mid]==v)
        return mid;
    return -1;
}

int bin1(int st, int dr, int v)
{
    int mid;
    while(st<dr)
    {
        mid=(st+dr)>>1;
        if(a[mid]<=v)
            st=mid+1;
        else
            dr=mid;
    }
    mid=(st+dr)>>1;
    if(a[mid]>v)
        mid--;
    return mid;
}

int bin2(int st, int dr, int v)
{
    int mid;
    while(st<dr)
    {
        mid=(st+dr)>>1;
        if(a[mid]<v)
            st=mid+1;
        else
            dr=mid;
    }
    mid=(st+dr)>>1;
    if(a[mid]<v)
        mid++;
    return mid;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    scanf("%d",&t);
    while(t--)
    {
        int v;int q;
        scanf("%d %d",&q,&v);
        switch(q)
        {
            case 0:
            {
                printf("%d\n",bin0(1,n,v));
                break;
            }
            case 1:
            {
                printf("%d\n",bin1(1,n,v));
                break;
            }
            case 2:
            {
                printf("%d\n",bin2(1,n,v));
                break;
            }
        }
    }
return 0;
}