#include <bits/stdc++.h>
#define NMAX 100005

using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");

int main() {
    int n, v[NMAX], m;
    in >> n;
    for (int i = 0; i < n; ++i)
        in >> v[i];
    in >> m;
    for (int i = 0; i < m; ++i) {
        int q, x;
        in >> q >> x;
        int mid;
        if (q == 0) {
            int low = 0, high = n - 1;
            bool gasit = 0;
            while (low <= high) {
                mid = low + (high - low) / 2;
                if (v[mid] == x) {
                    gasit = 1;
                    break;
                }
                if (v[mid] < x)
                    low = mid + 1;
                else
                    high = mid - 1;
            }
            if (!gasit){
                out << -1 << "\n";
                continue;
            }
            else {
                int j = mid;
                while(v[j] == x) j++;
                out << j << "\n";
            }
        }
        else if (q == 1) {
            int low = 0, high = n - 1;
            bool gasit = 0;
            while (low <= high) {
                mid = low + (high - low) / 2;
                if (v[mid] == x) {
                    gasit = 1;
                    break;
                }
                if (v[mid] < x)
                    low = mid + 1;
                else
                    high = mid - 1;
            }
            if (!gasit){
                out << mid << "\n";
                continue;
            }
            else {
                int j = mid;
                while(v[j] == x) j++;
                out << j << "\n";
            }
        }
        else if (q == 2) {
            int low = 0, high = n - 1;
            bool gasit = 0;
            while (low <= high) {
                mid = low + (high - low) / 2;
                if (v[mid] == x) {
                    gasit = 1;
                    break;
                }
                if (v[mid] < x)
                    low = mid + 1;
                else
                    high = mid - 1;
            }
            if (!gasit){
                out << mid + 1 << "\n";
                continue;
            }
            else {
                int j = mid;
                while(v[j] == x) j--;
                out << j + 2<< "\n";
            }
        }
    }
    return 0;
}