#include <fstream>
//#include <iostream>
#include <algorithm>
using namespace std;
ifstream cin ("cautbin.in");
ofstream cout ("cautbin.out");
int n, i, a[100001], m, test, x, p;
int main ()
{
    cin >> n;
    for (i=1; i<=n; i++)
        cin >> a[i];
    cin >> m;
    for (i=1; i<=m; i++){
        cin >> test >> x;
        if (test==0){
            p=upper_bound(a+1, a+n+1, x)-a;
            p--;
            if (a[p]!=x) cout << -1 << " ";
            else cout << p << '\n';
        }
        if (test==1){
            p=upper_bound(a+1, a+n+1, x)-a;
            p--;
            cout << p << '\n';
        }
        if (test==2){
            p=lower_bound(a+1, a+n+1, x)-a;
            cout << p << '\n';
        }
    }
    return 0;
}