#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+1]==sc && 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)/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+1]==sc && v[mid]==sc)
        {
            while(v[mid+1]==sc)
            {
                mid++;
            }
            break;
        }
        if(st+1==dr) break;
    }
    if(v[mid]!=sc)
    {
        mid--;
    }
    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-1]==sc && 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;
        switch(c)
        {
            case 0 : cout<<binsearch1(x)<<"\n";continue;
            case 1 : cout<<binsearch2(x)<<"\n";continue;
            case 2 : cout<<binsearch3(x)<<"\n";continue;
        }
    }
    return 0;
}