#include <cstdio>
#define NMax 100001

using namespace std;

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

    int n;
    scanf("%d", &n);
    int v[NMax];
    for(int i=1; i<=n; i++) scanf("%d", &v[i]);
    int m;
    scanf("%d", &m);
    for(int i=1; i<=m; i++) {
        int type, value;
        scanf("%d%d", &type, &value);

        if(type == 0) {
            int left = 1, right = n, mid;
            while(left <= right) {
                mid = left + (right - left) / 2;
                if(v[mid] <= value)
                    left = mid + 1;
                else
                    right = mid - 1;
            }
            mid = left + (right - left) / 2;
            if(v[mid] > value)
                mid--;
            if(v[mid] == value)
                printf("%d\n", mid);
            else
                printf("-1\n");
        }

        else if(type == 1) {
            int left = 1, right = n, mid;
            while(left < right) {
                mid = left + (right - left) / 2;
                if(v[mid] <= value)
                    left = mid + 1;
                else
                    right = mid;
            }
            mid = left + (right - left) / 2;
            if(v[mid] > value)
                mid--;
            printf("%d\n", mid);
        }
        else if(type == 2) {
            int left = 1, right = n, mid;
            while (left < right) {
                mid = left + (right - left) / 2;
                if(v[mid] < value)
                    left = mid + 1;
                else
                    right = mid;
            }
            mid = left + (right - left) / 2;
            if(v[mid] < value)
                mid++;
            printf("%d\n", mid);
        }
    }
}