#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

int n,m;
int a[100001];

int binarySearch0(int val, int left, int right){

    if (left <= right){
        int middle = (left+right)/2;

        if (a[middle] == val){
            //do binary search on the right to get the rightmost element
            int rightMost = binarySearch0(val, middle+1, right);

            if (rightMost == -1){
                return middle;
            } else {
                return rightMost;
            }
        }

        if (val > a[middle]){
            return binarySearch0(val, middle+1, right);
        }
        else {
            return binarySearch0(val, left, middle-1);
        }

    } else {
        return -1;
    }
}

int binarySearch1(int val, int left, int right){
     if (left <= right){
        int middle = (left+right)/2;

        if (a[middle] <= val && (middle == n || a[middle+1] > val)){
            return middle;
        }
        else

        if (val >= a[middle]){
            return binarySearch1(val, middle+1, right);
        }
        else {
            return binarySearch1(val, left, middle-1);
        }

    } else {
        return -1;
    }
}

int binarySearch2(int val, int left, int right){
     if (left <= right){
        int middle = (left+right)/2;

        if (a[middle] >= val && (middle == 1 || a[middle-1] < val)){
            return middle;
        }
        else
        if (val > a[middle]){
            return binarySearch2(val, middle+1, right);
        }
        else {
            return binarySearch2(val, left, middle-1);
        }

    } else {
        return -1;
    }
}

int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);

    scanf("%d", &n);

    for (int i=1; i<=n; i++){
        scanf("%d", &a[i]);
    }

    scanf("%d", &m);

    int op, val;
    for (int i=0; i<m; i++){
        scanf("%d %d", &op, &val);

        int pos;
        switch(op){
        case 0:
            pos = binarySearch0(val, 1, n);
            break;
        case 1:
            pos = binarySearch1(val, 1, n);
            break;
        default:
            pos = binarySearch2(val, 1, n);
            break;
        }

        printf("%d\n", pos);
    }


    return 0;
}