#include<fstream>
#include<algorithm>
using namespace std;

ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int V[100010];

int main () {
    int n, m, x, y, i, t;

    cin>>n;

    for (i = 1; i <= n; ++ i)
        cin>>V[i];

    cin>>m;

    while(m--) {
        cin>>t>>y;

        if(t == 0) {
            x = upper_bound(V + 1, V + n + 1, y) - V - 1;
            if (V[x] == y)
                cout<<x<<"\n";
            else cout<<"-1\n";
        } else if (t == 1) {
            x = lower_bound(V + 1, V + n + 1, y + 1)-V-1;
            cout<<x<<"\n";
        } else {
            x = upper_bound(V + 1, V + n + 1, y - 1) - V;
            cout<<x<<"\n";
        }
    }
}