#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)/2;
        if(a[mid]<=v)
            st=mid+1;
        else
            dr=mid-1;
    }
    mid=(st+dr)/2;
    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)/2;
        if(a[mid]<=v)
            st=mid+1;
        else
            dr=mid;
    }
    mid=(st+dr)/2;
    if(a[mid]>v)
        mid--;
    return mid;
}

int bin2(int st, int dr, int v)
{
    int mid;
    while(st<dr)
    {
        mid=(st+dr)/2;
        if(a[mid]<v)
            st=mid+1;
        else
            dr=mid;
    }
    mid=(st+dr)/2;
    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;
}