#include <fstream>

using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
const int N = 100009;
int v[N],n,m,cer,x;
int cbexc(int val)
{
    int st = 1,dr = n,poz = -1;
    while(st<=dr)
    {
        int mij = (st+dr)>>1;
        if(v[mij]<=val)
            poz = mij,
            st = mij+1;
        else
            dr = mij-1;
    }
    if(v[poz]==val)return poz;
    return -1;
}
int lb(int val)
{
    int st =1,dr=n,poz = -1;
    while(st<=dr)
    {
        int mij = (st+dr)>>1;
        if(v[mij]<=val)
            poz = mij,
            st = mij+1;
        else
            dr = mij-1;
    }
    if(v[poz] == val)return poz;
    return poz-1;
}
int ub(int val)
{
    int st =1,dr=n,poz = -1;
    while(st<=dr)
    {
        int mij = (st+dr)>>1;
        if(v[mij]>=val)
            poz = mij,
            dr = mij-1;
        else
            st = mij+1;
    }
    if(v[poz] == val)return poz;
    return poz+1;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>v[i];
    cin>>m;
    while(m--)
    {
        cin>>cer>>x;
        if(cer==0)
            cout<<cbexc(x)<<'\n';
        else if(cer==1)
            cout<<lb(x)<<'\n';
        else
            cout<<ub(x)<<'\n';
    }
    return 0;
}