#include <iostream>
#include <assert.h>
#include <vector>
#include <fstream>

int bin_lowx (std::vector<int> &v, int low, int high, int val) {
    int mid = (high - low) / 2 + low;

    if (low < high) {
        if (v[mid] == val) {
            if (mid < (int)v.size() - 1 && v[mid+1] != v[mid]) {
                return mid + 1;
            } else {
                return bin_lowx (v, mid + 1, high, val);
            }
        } else if (v[mid] < val) {
            return bin_lowx (v, mid + 1, high, val);
        } else {
            return bin_lowx (v, low, mid - 1, val);
        }
    } else {
        return v[mid] == val ? mid + 1 : -1;
    }
}

int bin_high (std::vector<int>& v, int low, int high, int val) {
    int mid = (high - low) / 2 + low;
    
    if (v[mid] <= val && (v[mid+1] > val || mid + 1 == v.size())) {
        return mid + 1;
    } else if (v[mid] > val) {
        return bin_high (v, low, mid - 1, val);
    } else if (v[mid] <= val && v[mid+1] <= val) {
        return bin_high (v, mid + 1, high, val);
    }
}

int bin_low (std::vector<int>& v, int low, int high, int val) {
    int mid = (high - low) / 2 + low;

    if (v[mid] >= val && v[mid-1] < val) {
        return mid + 1;
    } else if (v[mid] < val) {
        return bin_low (v, mid + 1, high, val);
    } else if (v[mid] >= val && v[mid] >= val) {
        return bin_low (v, low, mid - 1, val);
    }
}

int main() {
    std::ifstream fin ("cautbin.in");
    std::ofstream fout ("cautbin.out");
    std::vector<int> v;
    int type, val, no_elem, no_querry, aux;

    fin >> no_elem;

    for (int i = 0; i < no_elem; ++i) {
        fin >> aux;
        v.push_back (aux);
    }

    fin >> no_querry;

    for (int i = 0; i < no_querry; ++i) {
        fin >> type;
        fin >> val;

        switch (type) {
        case 0:
            fout << bin_lowx (v, 0, v.size() - 1, val) << "\n";
            break;
        case 1:
            fout << bin_high (v, 0, v.size() - 1, val) << "\n";
            break;
        case 2:
            fout << bin_low (v, 0, v.size() - 1, val) << "\n";
            break;
        }
    }

    fout.close();
    fin.close();

    return 0;
}