#include<cstdio>
#include<iostream>

using namespace std;
int v[100000], target;

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

int cautbin1(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(mid, hi);
    }else{
        return cautbin1(lo, mid);
    }
}

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

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