#include <fstream>

using namespace std;
int i,x,p,mid,st,dr,n,v[100001],c,m;
ifstream cin ("cautbin.in");
ofstream cout ("cautbin.out");
int binsearch1(int sc)
{
    st=1;
    dr=n;
    mid=(1+n)/2;
    while(st!=dr)
    {
        if(sc>v[mid])
        {
            st=mid;
            mid=(st+dr)/2;
        }
        if(sc<v[mid])
        {
            dr=mid;
            mid=(st+dr)/2;
        }
        if(v[mid]==sc)
        {
            while(v[mid+1]==sc)
            {
                mid++;
            }
            break;
        }
        if(st+1==dr) break;
    }
    if(v[mid]!=sc) mid=-1;
    return mid;
}
int binsearch2(int sc)
{
    st=1;
    dr=n;
    mid=(1+n+1)/2;
    while(st!=dr)
    {
        if(sc>=v[mid])
        {
            st=mid;
            mid=(st+dr+1)/2;
        }
        if(sc<v[mid])
        {
            dr=mid-1;
            mid=(st+dr+1)/2;
        }

    }
    return mid;

}
int binsearch3(int sc)
{
    st=1;
    dr=n;
    mid=(1+n)/2;
    while(st!=dr)
    {
        if(sc>v[mid])
        {
            st=mid;
            mid=(st+dr)/2;
        }
        if(sc<v[mid])
        {
            dr=mid;
            mid=(st+dr)/2;
        }
        if(v[mid]==sc)
        {
            while(v[mid-1]==sc)
            {
                mid--;
            }
            break;
        }
        if(st+1==dr) break;
    }
    if(v[mid]!=sc)
    {
        mid++;
    }
    return mid;

}
int main()
{
    cin>>n;
    for(i=1; i<=n; i++)
        cin>>v[i];
    cin>>m;
    for(i=1; i<=m; i++)
    {
        cin>>c;
        cin>>x;
        if(c==0)
            cout<<binsearch1(x)<<"\n";
        if(c==1)
            cout<<binsearch2(x)<<"\n";
        if(c==2)
            cout<<binsearch3(x)<<"\n";
    }
    return 0;
}