#pragma GCC optimize("O2, unroll-loops")
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vpii = vector<pii>;
 
const int MOD = 1000000007;
const int INF = 1e9;
const ll LINF = 1e18;
 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (b) - 1; i >= (a); i--)
#define ternary(cond, a, b) ((cond) ? (a) : (b))
 
void fastIO(string input = "", string output = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    if (!input.empty()) {
        freopen(input.c_str(), "r", stdin);
    }
    if (!output.empty()) {
        freopen(output.c_str(), "w", stdout);
    }
}
 
template<typename T>
void read(vector<T>& v, int n) {
    v.resize(n);
    rep(i, 0, n) cin >> v[i];
}
 
template<typename T>
void print(const vector<T>& v) {
    rep(i, 0, sz(v)) {
        cout << v[i];
        if(i < sz(v) - 1) cout << ' ';
    }
    cout << '\n';
}
 
ll power(ll a, ll b, ll mod = MOD) {
    ll res = 1;
    a %= mod;
    while(b > 0) {
        if(b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
 
ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}
 
ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}
 
ll modinv(ll a, ll mod = MOD) {
    return power(a, mod - 2, mod);
}
 
bool isPrime(ll n) {
    if(n < 2) return false;
    if(n == 2 || n == 3) return true;
    if(n % 2 == 0 || n % 3 == 0) return false;
    for(ll i = 5; i * i <= n; i += 6) {
        if(n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}
 
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
 
void solve() {
    int n;
    cin >> n;
    
    vi v(n);
    rep(i, 0, n)
        cin >> v[i];
    
    int m;
    cin >> m;
    
    rep(i, 0, m) {
        int t, x;
        cin >> t >> x;
        
        if(t == 0) {
            int it = upper_bound(all(v), x) - v.begin() - 1;
            cout << ternary(v[it] == x, it + 1, -1) << '\n';
        } else if(t == 1) {
            cout << upper_bound(all(v), x) - v.begin() << '\n';
        } else {
            cout << lower_bound(all(v), x) - v.begin() + 1 << '\n';
        }
    }
}
 
int main() {
    fastIO("cautbin.in", "cautbin.out");
 
    // fastIO();
 
    int t = 1;
    // cin >> t;
 
    while(t--) {
        solve();
    }
 
    return 0;
}