#include <fstream>
int bsearch2 (int *v, int start, int end, int sought) {
int mid;
while (start < end) {
mid = (start + end) / 2;
if (v[mid] < sought)
start = mid + 1;
else
end = mid;
}
mid = (start + end) / 2;
if (v[mid] < sought)
mid++;
return mid + 1;
}
int binary(int* v, int size, int sought, int command) {
int i = 0, step;
if (command == 0 || command == 1) {
for (step = 1; step < size; step <<= 1);
int prev = step - 1;
do {
if (i + step < size && v[i + step] <= sought) {
i += step;
}
prev = i + step;
step >>= 1;
} while (prev > (step + i));
if (command == 0 && prev < size && v[prev] != sought)
return -1;
if (command == 1 && prev < size && v[prev] > sought)
return -1;
return prev + 1;
}
if (command == 2) {
return bsearch2(v, step, step << 1, sought);
}
return -1;
}
int main() {
std::ifstream f("cautbin.in");
std::ofstream g("cautbin.out");
int N;
f >> N;
//std::cout << N << "\n";
int* a = new int[N];
for (int i = 0; i < N; ++i) {
f >> a[i];
}
int c;
int command, s;
f >> c;
for (int i = 0; i < c; ++i) {
f >> command >> s;
g << binary(a, N, s, command) << "\n";
//std::cout << i << "\n";
}
delete[] a;
}