#include <bits/stdc++.h>
 
using namespace std;
 
string __fname = "cautbin"; ifstream in (__fname + ".in"); ofstream out (__fname + ".out"); 
#define cin in 
#define cout out
 
 
int st(int r, int n, vector<int> &a){
    int L = 0, R = n-1;
    int mid;
    int ans = -1;
    while(L <= R){
        mid = L + (R-L) / 2;
        if(a[mid] == r){
            ans = mid;
            L = mid + 1;
        }
        if(a[mid] < r){
            L = mid + 1;
        }
        else if(a[mid] > r){
            R = mid - 1;
        }
    }
    return ans;
}
 
 
int nd(int r, int n, vector<int> &a){
    int L = 0, R = n-1;
    int mid;
    int ans = -1;
    while(L <= R){
        mid = L + (R-L) / 2;
        if(a[mid] <= r){
            ans = mid;
            L = mid + 1;
        }
        else{
            R = mid - 1;
        }
    }
    return ans;
}
 
int rd(int r, int n, vector<int> &a){
    int L = 0, R = n-1;
    int mid;
    int ans = -1;
    while(L <= R){
        mid = L + (R-L) / 2;
        if(a[mid] >= r){
            ans = mid;
            R = mid - 1;
        }
        else{
            L = mid + 1;
        }
    }
    return ans;
}
 
 
int main()
 
{   
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0;i < n; i++){
        cin >> a[i];
    }
    int t;
    cin >> t;
    while(t--){
        int q, r;
        cin >> q >> r;
        if(q == 0){
            int rs = st(r, n, a);
            if(rs == -1) cout << rs << endl;
            else cout << rs + 1 << endl;
        }
        else if(q == 1){
            cout << nd(r, n, a) + 1<< endl;
        }
        else{
            cout << rd(r, n, a) + 1<< endl;
        }
    }
    return 0;
}