#include <fstream>
using namespace std;

int n, v[100005], Q, T, x;
int binary_search1(int val)
{
    int i, step;
    for(step = 1; step <= n; step <<= 1);
    for(i = 0; step; step >>= 1)
        if(i + step <= n && v[i + step] <= val)
           i += step;
    if(v[i] == val) return i;
     else return -1;
}
int binary_search2(int val)
{
    int i, step;
    for(step = 1; step <= n; step <<= 1);
    for(i = 0; step; step >>= 1)
        if(i + step <= n && v[i + step] <= val)
           i += step;
    return i;
}
int binary_search3(int val)
{
    int i, step;
    for(step = 1; step <= n; step <<= 1);
    for(i = n; step; step >>= 1)
        if(i - step > 0 && v[i - step] >= val)
           i -= step;
    return i;
}
int main()
{
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    fin >> n;
    for(int i = 1; i <= n; i++) fin >> v[i];
    fin >> T;
    for(int i = 1; i <= T; i++){
        fin >> Q >> x;
        if(Q == 0) fout << binary_search1(x) << '\n';
        else if(Q == 1) fout << binary_search2(x) << '\n';
        else fout << binary_search3(x) << '\n';
    }
    return 0;
}