#include<cstdio>
#include<iostream>

using namespace std;

int cautbin0(int v[100000], int target, int lo, int hi){
    int mid = lo + (hi - lo)/2;
    if (mid == lo){
        if (v[mid] == target)
            return mid + 1;
        return -1;
    }
    if(v[mid] <= target){
        return cautbin0(v, target, mid, hi);
    }else{
        return cautbin0(v, target, lo, mid);
    }
}

int cautbin1(int v[100000], int target, int lo, int hi){
    int mid = lo + (hi - lo)/ 2;
    if (mid == lo){
        if (v[mid + 1] > target)
            return mid + 1;
            else return mid + 2;
    }
    if (v[mid] <= target){
        return cautbin1(v, target, mid, hi);
    }else{
        return cautbin1(v, target, lo, mid);
    }
}

int cautbin2(int v[100000], int target, int lo, int hi){
    int mid = lo + (hi - lo)/2;
    if (mid == lo)
        return mid + 2;
    if (v[mid] < target){
        return cautbin2(v, target, mid, hi);
    }else{
        return cautbin2(v, target, lo, mid);
    }
}

int main(){
    int v[100000];
    int target, n, m, q;
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> v[i];
    }
    cin >> m;
    for (int i = 0; i < m; i++){
        cin >> q >> target;
        if (q == 0){
            cout << cautbin0(v, target, 0, n-1) << endl;
        }
        if (q == 1){
            cout << cautbin1(v, target, 0, n-1) << endl;
        }
        if (q == 2){
            cout << cautbin2(v, target, 0, n-1) << endl;
        }
    }
}