#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> arr;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

void solve0(int num, int left, int right, int &pos) {
    if (left > right) {
        if (pos == -1) {
            fout << "-1\n";
        } else {
            fout << pos + 1 << "\n";
        }
        return;
    }
    int mid = left + (right - left) / 2;
    if (arr[mid] == num) {
        pos = mid;
        solve0(num, mid + 1, right, pos);
    } else if (arr[mid] > num) {
        solve0(num, left, mid - 1, pos);
    } else {
        solve0(num, mid + 1, right, pos);
    }
}

void solve1(int num, int left, int right, int &pos) {
    if (left > right) {
        fout << pos + 1 << "\n";
        return;
    }
    int mid = left + (right - left) / 2;
    if (arr[mid] <= num) {
        pos = mid;
        solve1(num, mid + 1, right, pos);
    } else {
        solve1(num, left, mid - 1, pos);
    }
}

void solve2(int num, int left, int right, int &pos) {
    if (left > right) {
        fout << pos + 1 << "\n";
        return;
    }
    int mid = left + (right - left) / 2;
    if (arr[mid] >= num) {
        pos = mid;
        solve2(num, left, mid - 1, pos);
    } else {
        solve2(num, mid + 1, right, pos);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    fin >> n;
    arr.resize(n);
    for (int i = 0; i < n; ++i) {
        fin >> arr[i];
    }
    fin >> m;
    while (m--) {
        int op, num;
        fin >> op >> num;
        int pos = -1;
        if (op == 0) {
            solve0(num, 0, n - 1, pos);
        } else if (op == 1) {
            solve1(num, 0, n - 1, pos);
        } else {
            solve2(num, 0, n - 1, pos);
        }
    }
    return 0;
}