#include <iostream>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <string>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <iomanip>

using namespace std;

#define ll long long

int n, m;
vector<int> values;

void ReadData() {
    cin >> n;

    for(int i = 0; i < n; i++){
        int value = 0;
        cin >> value;
        values.push_back(value);
    }
    cin >> m;
}

int binarySearch(int value, int low, int high){
    while( low <= high){
        int mid = low + (high - low)/2;
        if(values[mid] == value) return mid;
        else if(values[mid] > value) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

int lowerBound(int value){
    int low = 0;
    int high = n - 1;
    int lower = value;
    while( low <= high){
        int mid = low + (high - low)/2;
        if(values[mid] == value) return mid;
        else if(values[mid] > value) high = mid - 1;
        else {
            lower = mid;
            low = mid + 1;
        }
    }
    return lower;
}

int upperBound(int value){
    int low = 0;
    int high = n - 1;
    int upper = value;
    while( low <= high){
        int mid = low + (high - low)/2;
        if(values[mid] == value) return mid;
        else if(values[mid] > value){
            upper = mid;
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    }
    return upper;
}

void Solve() {
    int ops = 0;
    int x = 0;
    for(int i = 0; i < m; i++){
        cin >> ops >> x;

        if(ops == 0){
            int index = binarySearch(x, 0, n - 1);
            if (index == -1) {
                cout << -1 << "\n";
                continue;
            }
            int maxIndex = index;
            while(index != - 1){
                maxIndex = max(index, maxIndex);
                index = binarySearch(x, index + 1, n - 1);
            }
            cout << maxIndex + 1 << "\n";
        } else if(ops == 1){
            if(binarySearch(x, 0, n - 1) != -1){
                int index = binarySearch(x, 0, n - 1);
                int maxIndex = index;
                while(index != - 1){
                    maxIndex = max(index, maxIndex);
                    index = binarySearch(x, index + 1, n - 1);
                }
                cout << maxIndex + 1 << "\n";
            } else {
                cout << lowerBound(x) + 1 << "\n";
            }
        } else {
            if(binarySearch(x, 0, n - 1) != -1){
                int index = binarySearch(x, 0, n - 1);
                int minIndex = index;
                while(index != - 1){
                    minIndex = min(index, minIndex);
                    index = binarySearch(x, 0, index - 1);
                }
                cout << minIndex + 1 << "\n";
            } else {
                cout << upperBound(x) + 1 << "\n";
            }
        }
    } 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);

    int t = 1;
    while (t--) {
        ReadData();
        Solve();   
    }
    return 0;
}