#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(st==dr)
        if(x==v[st]) return m;
        else return -1;
    else
    {
        if(x>=v[m+1]) return zero(x, m+1, dr);
        if(x>v[m]) return -1;
        if(x==v[m]) return m;
        if(m-1>=st) return zero(x, st, m-1);
        return -1;
    }
}
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)
                if(x>v[n])cout<<n<<'\n';
                else cout<<unu(x, 1, n)<<'\n';
             else if(t==2)
                    if(x<v[1])cout<<1<<'\n';
                    else cout<<doi(x, 1, n)<<'\n';
    }
    return 0;
}