#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

vector <int> a;
int m,x,y;

void read()
{
    int n;
    cin >> n;
    a.resize(n);
    for (int i=0; i<a.size(); cin >> a[i++]);
}

main()
{
    read();
    cin >> m;
    for (; m ; m--)
    {
        cin >> x >> y;
        if (x==1) cout << lower_bound(a.begin(), a.end(), y + 1) - a.begin() << '\n';
        if (x==2) cout << upper_bound(a.begin(), a.end(), y - 1) - a.begin()+1 << '\n';
        if (x==0)
        {
            x=upper_bound(a.begin(),a.end(),y)-a.begin();
            if (x<=a.size() && x>=0 && a[x-1]==y) cout << x << '\n';
            else cout << "-1\n";// << x << ' ' << (x<a.size()) << ' ' << (x>=0) << ' ' << (a[x-1]==y) << '\n';
        }
    }
}