#include <bits/stdc++.h>

string fname = "cautbin"; ifstream in (fname + ".in"); ofstream out (__fname + ".out"); 
#define cin in 
#define cout out
using namespace std;

int st(int r, int n, vector<int> a){
    int L = 0, R = n-1;
    int mid;
    while(L <= R){
        mid = L + (R-L) / 2;
        if(a[mid] == r && a[mid + 1] > r){
            return mid + 1;
        }
        if(a[mid] <= r){
            L = mid + 1;
        }
        else{
            R = mid - 1;
        }
    }
    return -1;
}


int nd(int r, int n, vector<int> a){
    int L = 0, R = n-1;
    int mid;
    while(L <= R){
        mid = L + (R-L) / 2;
        if(a[mid] <= r && a[mid + 1] > r){
            return mid + 1;
        }
        if(a[mid] >= r){
            L = mid + 1;
        }
        else{
            R = mid - 1;
        }
    }
    return -1;
}

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