#include <cstdio>
#include <cassert>
#define in "cautbin.in"
#define out "cautbin.out"
#define N 100003

using namespace std;

unsigned int v[N],n,m;

inline void T0(int k)
{
    bool gasit=false;

    int st,dr,mid;
    st=1; dr=n;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(v[mid]<=k) st=mid+1;
            else dr=mid-1;
    }

    mid=(st+dr)/2;
    if(v[mid]>k) --mid;
    if(v[mid]==k) gasit=true;

    if(!gasit) printf("-1\n");
        else printf("%d\n",mid);
}

inline void T1(int k)
{
    int st,dr,mid;
    st=1; dr=n;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(v[mid]<=k) st=mid+1;
            else dr=mid-1;
    }

    mid=(st+dr)/2;
    if(v[mid]>k) --mid;

    printf("%d\n",mid);
}

inline void T2(int k)
{
    int st,dr,mid;
    st=1; dr=n;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(v[mid]<k) st=mid+1;
            else dr=mid-1;
    }

    mid=(st+dr)/2;

    if(v[mid]<k) ++mid;

    printf("%d\n",mid);
}


int main()
{
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);

    scanf("%ud",&n);
    for(int i=1; i<=n; ++i) scanf("%ud",&v[i]);
    assert(n<=N);
    scanf("%ud",&m);
    while(m--)
    {
        int Q,k;
        scanf("%d%d",&Q,&k);
        switch(Q)
        {
            case 0: T0(k); break;
            case 1: T1(k); break;
            default : T2(k); break;
        }
    }

    fclose(stdin); fclose(stdout);
    return 0;
}