#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 + 1;
}
 
 
int nd(int r, int n, vector<int> &a){
    int L = 0, R = n-1;
    int mid;
    int ans;
    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 + 1;
}
 
int rd(int r, int n, vector<int> &a){
    int L = 0, R = n-1;
    int mid;
    int ans;
    while(L <= R){
        mid = L + (R-L) / 2;
        if(a[mid] >= r){
            ans = mid;
            R = mid - 1;
        }
        else{
            L = mid + 1;
        }
    }
    return ans + 1;
}
 
 
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){
            cout << st(r, n, a) << endl;
        }
        else if(q == 1){
            cout << nd(r, n, a) << endl;
        }
        else{
            cout << rd(r, n, a) << endl;
        }
    }
    return 0;
}