#include <cstdio>
using namespace std;
int v[100005],n,m,i,x,j,c,stg,dr,poz,v2[100005],q;
int cautpentru0(int stg,int dr,int x)
{
     while(stg<=dr)
            {poz=(stg+dr)/2;
            if(v[poz]<=x)
            stg=poz+1;
            else
                dr=poz-1;
            }
        poz=(stg+dr)/2;
    if(v[poz]>x)
        poz--;
    if(v[poz]==x)
        return poz;
    return -1;
}
int cautpentru1(int stg,int dr,int x)
{
            while(stg<=dr)
            {poz=(stg+dr)/2;
            if(v[poz]<=x)
            stg=poz+1;
            else
                dr=poz-1;
            }
             poz=(stg+dr)/2;
            if(v[poz]>x)
                poz--;
             return poz;
}
int cautpentru2(int stg,int dr,int x)
{
            while(stg<=dr)
            {poz=(stg+dr)/2;
            if(v[poz]<x)
            stg=poz+1;
            else
            dr=poz-1;
            }
            poz=(stg+dr)/2;
             if(v[poz]<x)
             poz++;
             return poz;
}
int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    scanf("%d",&m);
    for(j=1;j<=m;j++)
    {
        scanf("%d%d",&c,&x);
        if(c==0)
            printf("%d\n",cautpentru0(1,n,x));
         if(c==1)
            printf("%d\n",cautpentru1(1,n,x));
             if(c==2)
            printf("%d\n",cautpentru2(1,n,x));
    }
    return 0;
}