#include <fstream>

using namespace std;

ifstream cin("cautbin.in");
ofstream cout("cautbin.out");

int n, m, i, t, x, v[100001];

int zero(int x, int st, int dr)
{
    int m;
    m=(st+dr)/2;
    if (m==st)
        if (v[m+1]==x) return m+1;
        else
            if (v[m]==x) return m;
            else return -1;
    else
        if (v[m]<=x) return zero(x, m, dr);
        else return zero(x, st, m);
}
int unu(int x, int st, int dr)
{
    int m;
    m=(st+dr)/2;
    if(x>=v[m+1]) return unu(x, m+1, dr);
    if(x>=v[m])return m;
    return unu(x, st, m-1);
}
int doi(int x, int st, int dr)
{
    int m;
    m=(st+dr)/2;
    if(x<=v[m-1]) return doi(x, st, m-1);
    if(x<=v[m])return m;
    return doi(x, m+1, dr);
}
int main()
{
    cin>>n;
    for(i=1; i<=n; i++) cin>>v[i];
    cin>>m;
    for(i=1; i<=m; i++)
    {
        cin>>t>>x;
        if(t==0) cout<<zero(x, 1, n)<<'\n';
        else if(t==1) cout<<unu(x, 1, n)<<'\n';
             else if(t==2) cout<<doi(x, 1, n);
    }
    return 0;
}