#include <iostream>
#include <fstream>

using namespace std;

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

const int NMax = 1e5;

int n, m;
int v[NMax + 5];

void Read(){
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> v[i];
    fin >> m;
}

int BinarySearch0(int value, int left, int right){
    if (left == right){
        if (value == v[left])
            return left;
        return -1;
    }
    int mid = (left + right) >> 1;
    if (v[mid] == value)
        return max(mid, BinarySearch0(value, mid + 1, right));
    if (v[mid] < value)
        return BinarySearch0(value, mid + 1, right);
    if (v[mid] > value)
        return BinarySearch0(value, left, mid - 1);
}

int BinarySearch1(int value, int left, int right){
    if (left == right){
        if (value >= v[left])
            return left;
        return -1;
    }
    int mid = (left + right) >> 1;
    if (v[mid] <= value)
        return max(mid, BinarySearch1(value, mid + 1, right));
    if (v[mid] > value)
        return BinarySearch1(value, left, mid - 1);
}

int BinarySearch2(int value, int left, int right){
     if (left == right){
        if (value <= v[left])
            return left;
        return NMax;
    }
    int mid = (left + right) >> 1;
    if (v[mid] >= value)
        return min(mid, BinarySearch2(value, left, mid - 1));
    if (v[mid] < value)
        return BinarySearch2(value, mid + 1, right);
}

void Print(){
    while (m--){
        int type, value;
        fin >> type >> value;
        if (type == 0)
            fout << BinarySearch0(value, 1, n) << '\n';
        if (type == 1)
            fout << BinarySearch1(value, 1, n) << '\n';
        if (type == 2)
            fout << BinarySearch2(value, 1, n) << '\n';
    }
}

int main(){
    Read();
    Print();
    return 0;
}