// Binary_search.cpp : Defines the entry point for the console application.
//
#include <stdio.h>
#define maxn 100005
int Upper_bound(int n, int val, int V[]) {
int left = 0, right = n - 1, mid, pos;
while (left <= right) {
mid = (left + right) >> 1;
if (V[mid] <= val) {
pos = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return pos;
}
int Lower_bound(int n, int val, int V[]) {
int left = 0, right = n - 1, mid, pos;
while (left <= right) {
mid = (left + right) >> 1;
if (V[mid] < val) {
left = mid + 1;
} else {
pos = mid;
right = mid - 1;
}
}
return pos;
}
int main() {
FILE *fin = fopen("cautbin.in", "r");
FILE *fout = fopen("cautbin.out", "w");
int V[maxn], n, m, type, i, x, pos;
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", &type, &x);
if (type == 0) {
pos = Upper_bound(n, x, V);
if (V[pos] != x) {
fprintf(fout, "-1 \n");
} else {
fprintf(fout, "%d \n", pos + 1);
}
} else if (type == 1) {
pos = Upper_bound(n, x, V);
fprintf(fout, "%d\n", pos + 1);
} else {
pos = Lower_bound(n, x, V);
fprintf(fout, "%d\n", pos + 1);
}
}
fclose(fin);
fclose(fout);
return 0;
}