#include<cstdio>
#define MAX_N 100000

int v[MAX_N], n, m;

int binarySearch0(int val) {
    int left, right, mid, poz;
    left = 0; right = n - 1;
    poz = -2;
    while(left <= right) {
        mid = (left + right) >> 1;
        if(v[mid] == val) {
            poz = mid;
            left = mid + 1;
        } else if(val < v[mid])
            right = mid - 1;
        else left = mid + 1;
    }
    return poz;
}

int binarySearch1(int val) {
    int left, right, mid, poz;
    left = 0; right = n - 1;
    poz = -1;
    while(left <= right) {
        mid = (left + right) >> 1;
        if(v[mid] <= val) {
            poz = mid;
            left = mid + 1;
        } else right = mid - 1;
    }
    return poz;
}

int binarySearch2(int val) {
    int left, right, mid, poz;
    left = 0; right = n - 1;
    poz = -1;
    while(left <= right) {
        mid = (left + right) >> 1;
        if(v[mid] >= val) {
            poz = mid;
            right = mid - 1;
        } else left = mid + 1;
    }
    return poz;
}

int main() {
    int i, op, x;
    FILE* fin, *fout;
    fin = fopen("cautbin.in","r");
    fout = fopen("cautbin.out","w");
    fscanf(fin,"%d",&n);
    for(i = 0; i < n; i++)
        fscanf(fin,"%d",&v[i]);
    fscanf(fin,"%d",&m);
    for(i = 0; i < m; i++) {
        fscanf(fin,"%d%d",&op,&x);
        if(op == 0)
            fprintf(fout,"%d\n",binarySearch0(x)+1);
        else if(op == 1)
            fprintf(fout,"%d\n",binarySearch1(x)+1);
        else fprintf(fout,"%d\n",binarySearch2(x)+1);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}