#include <fstream>

using namespace std;
ifstream cin ("cautbin.in");
ofstream cout ("cautbin.out");
int v[100005];
int n,m;
int binar0(int x)
{
    int st = -1;
    int dr = n + 1;
    while(dr - st > 1)
    {
        int mij = (st+dr)/2;
        if(v[mij] > x)
            dr = mij;
        else
            st = mij;
    }
    if(v[st]!=x)
        return -1;
    return st;
}
int binar1(int x)
{
    int st = -1;
    int dr = n + 1;
    while(dr - st > 1)
    {
        int mij = (st+dr)/2;
        if(v[mij] > x)
            dr = mij;
        else
            st = mij;
    }
    return st;
}
int binar2(int x)
{
    int st = -1;
    int dr = n + 1;
    while(dr - st > 1)
    {
        int mij = (st+dr)/2;
        if(v[mij] < x)
            st = mij;
        else
            dr = mij;
    }
    return dr;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++)
        cin >> v[i];
    cin >> m;
    for(int i=1;i<=m;i++)
    {
        int t,x;
        cin >> t >> x;
        if(t==0)
        {
            cout << binar0(x) << '\n';
            continue;
        }
        if(t==1)
        {
            cout << binar1(x) << '\n';
            continue;
        }
        cout << binar2(x) << '\n';
    }
    return 0;
}