#include <iostream>
#include <fstream>
using namespace std;

int n, m;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int Bsearch0(int find, int left, int right, int vec[]) {
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (vec[mid] == find) {
            break;
        } else if (find > vec[mid]) {
            left = mid + 1;
        } else if (find < vec[mid]) {
            right = mid - 1;
        }
    }
    if (vec[mid] != find) {
        return -1;
    } else {
        while (mid <= n && vec[mid] == find) {
            ++mid;
        }
        return mid - 1;
    }
}

int Bsearch1(int find, int left, int right, int vec[]) {
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (vec[mid] == find) {
            break;
        }
        if (find > vec[mid]) {
            left = mid + 1;
        } else if (find < vec[mid]) {
            right = mid - 1;
        }
    }
    if (vec[mid] == find) {
        while (mid <= n && vec[mid] == find) {
            ++mid;
        }
        return mid - 1;
    } else {
        while (mid >= 1 && vec[mid] > find) {
            --mid;
        }
        if (mid < 1) {
            return mid + 1;
        }
        return mid;
    }
}
int Bsearch2(int find, int left, int right, int vec[]) {
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        //cout << left << ' ' << right << '\n';
        if (vec[mid] == find) {
            break;
        } else if (find > vec[mid]) {
            left = mid + 1;
        } else if (find < vec[mid]) {
            right = mid - 1;
        }
    }
    if (vec[mid] == find) {
        while (mid >= 1 && vec[mid] == find) {
            --mid;
        }
        return mid + 1;
    } else {
        while (mid <= n && vec[mid] < find) {
            ++mid;
        }
        if (mid > n) {
            return mid - 1;
        }
        return mid;
    }
}
int main() {
    fin >> n;
    int vec[n];
    for (int i = 1; i <= n; ++i) {
        fin >> vec[i];
    }
    fin >> m;
    while (m--) {
        int condition, x;
        fin >> condition >> x;
        if (condition == 0) {
            fout << Bsearch0(x, 1, n, vec) << '\n';
        } else if (condition == 1) {
            fout << Bsearch1(x, 1, n, vec) << '\n';
        } else if (condition == 2) {
            fout << Bsearch2(x, 1, n, vec) << '\n';
        }
      }
    return 0;
}