#include<cstdio>
#include<cstdlib>
int v[100001];
int cb0(int l,int r,int k)
{
    int m;
    while(l<=r)
    {
        m=(l+r)/2;
        if(v[m]<=k)
           l=m+1;
        else
           r=m-1;
    }
    m=(l+r)/2;
    if(v[m]>k) m--;
    if(v[m]==k)
       return m;
    return -1;
}    
int cb1(int l,int r,int k)
{
    int m;
    while(l<r)
    {
        m=(l+r)/2;
        if(v[m]<=k)
            l=m+1;
        else
            r=m;
    }
    m=(l+r)/2;
    if(v[m]>k) m--;
    return m;
}
int cb2(int l,int r,int k)
{
    int m;
    while(l<r)
    {
        m=(l+r)/2;
        if(v[m]<k)
            l=m+1;
        else
            r=m;
    }
    m=(l+r)/2;
    if(v[m]<k) m++;
    return m;
}

int main()
{
    int i,n,m,tip,val;
    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(i=1;i<=m;i++)
    {
        scanf("%d %d",&tip,&val);
        if(tip==0) printf("%d\n",cb0(1,n,val));
        else if(tip==1) printf("%d\n",cb2(1,n,val));
        else if(tip==2) printf("%d\n",cb1(1,n,val));
    }
    return 0;
}