#include <fstream>

using namespace std;
ifstream cin ("cautbin.in");
ofstream cout ("cautbin.out");
int v[100001];
int BSL(int st,int dr,int x)
{
    int med,last=-1;
    while(st<=dr)
    {
        med=(st+dr)/2;

        if(x<=v[med])
        {
            last = med;
            dr=med-1;
        }
        else
            st=med+1;
    }
    return last;
}
int bsr(int st, int dr, int x){
int med, last=-1;
while(st<=dr){
    med=(st+dr)/2;
    if(x>=v[med]){
        last=med;
        st=med+1;
    }
    else
        dr=med-1;
}
return last;
}
int bs (int st, int dr, int x)
{
    int med;
    while (st<=dr)
    {
        med=(st+dr)/2;
        if (v[med]==x)
        {
            return 1;
        }
        else
        {
            if (v[med>x])
            {
                dr=med-1;
            }
            else
                st=med+1;
        }
    }
    return 0;
}
int main()
{
    int n, i, m, q, a, R;
    cin>>n;
    for (i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    cin>>m;
    for (i=1;i<=m;i++)
    {
        cin>>q>>a;
        if (q==0)
        {
        if (bs(1, n, a)==1)
        {
            R=bsr(1, n, a);
            cout<<R<<"\n";
        }
        else
            cout<<"-1"<<"\n";
        }
        if (q==1)
        {
    cout<<bsr(1, n, a)<<"\n";
        }
        if (q==2)
        {
            cout<<BSL(1, n, a)<<"\n";
        }
    }
    return 0;
}