#include <bits/stdc++.h>
	
#define MAXSZ 100010
	
 
	
using namespace std;
	
 
	
ifstream fin("cautbin.in");
	
ofstream fout("cautbin.out");
	
 
	
int binarySearch(int n, int arr[], int x) {
	
    int lo = 0, hi = n;
	
    while (lo <= hi) {
	
        int mid = lo + (hi - lo) / 2;
	
        if (arr[mid] <= x)
	
            lo = mid + 1;
	
        else
	
            hi = mid - 1;
	
    }
	
 
	
    return arr[hi] == x ? hi : -1;
	
}
	
 
	
int lowerBound(int n, int arr[], int x) {
	
    int lo = 1, hi = n;
	
    while (lo <= hi) {
	
        int mid = lo + (hi - lo) / 2;
	
        if (arr[mid] <= x)
	
            lo = mid + 1;
	
        else
	
            hi = mid - 1;
	
    }
	
 
	
    return hi;
	
}
	
 
	
int higherBound(int n, int arr[], int x) {
	
    int lo = 1, hi = n;
	
    while (lo <= hi) {
	
        int mid = lo + (hi - lo) / 2;
	
        if (arr[mid] >= x)
	
            hi = mid - 1;
	
        else
	
            lo = mid + 1;
	
    }
	
 
	
    return lo;
	
}
	
 
	
int main() {
	
    int n, arr[MAXSZ];
	
    fin >> n;
	
    for (int i = 1; i <= n; i++)
	
        fin >> arr[i];
	
 
	
    int m;
	
    fin >> m;
	
    for (int q = 0; q < m; q++) {
	
        int t, x;
	
        fin >> t >> x;
	
        switch (t) {
	
            case 0:
                fout << binarySearch(n, arr, x) << '\n';
                break;
	
            case 1:
                fout << lowerBound(n, arr, x) << '\n';
                break;
	
            case 2:
                fout << higherBound(n, arr, x) << '\n';
                break;
        }
    }
	
    return 0;
}