#include<cstdio>
#define MAX_N 100000
using namespace std;

int v[MAX_N+1], n, m;

int binarySearch0(int val) {
    int b, e, mid, pos;
    b = 1; e = n; pos = -1;
    while(b <= e) {
        mid = (b + e) >> 1;
        if(v[mid] == val) {
            pos = mid;
            b = mid + 1;
        } else if(val < v[mid])
            e = mid - 1;
        else b = mid + 1;
    }
    return pos;
}

int binarySearch1(int val) {
    int b, e, mid, pos;
    b = 1; e = n; pos = -1;
    while(b <= e) {
        mid = (b + e) >> 1;
        if(v[mid] <= val) {
            pos = mid;
            b = mid + 1;
        } else e = mid - 1;
    }
    return pos;
}

int binarySearch2(int val) {
    int b, e, mid, pos;
    b = 1; e = n; pos = -1;
    while(b <= e) {
        mid = (b + e) >> 1;
        if(v[mid] >= val) {
            pos = mid;
            e = mid - 1;
        }
        else b = mid + 1;
    }
    return pos;
}

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 = 1; 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)
            fprintf(fout,"%d\n",binarySearch0(x));
        else if(op == 1)
            fprintf(fout,"%d\n",binarySearch1(x));
        else fprintf(fout,"%d\n",binarySearch2(x));
    }
    fclose(fin);
    fclose(fout);
    return 0;
}