#include <fstream>

using namespace std;

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

int v[100001];

int cautbin(int val, int n){
int pos = 0;
for(int a = (1 << 20); a > 0; a /= 2)
    if(pos + a <= n && v[pos + a] <= val)
        pos += a;
    if(v[pos] == val)
        return pos;
    else return -1;
}

int cautbin1(int val, int n){
int pos = 0;
for(int a = (1 << 20); a > 0; a /= 2)
    if(pos + a <= n && v[pos + a] <= val)
        pos += a;
    if(v[pos] <= val)
        return pos;
}

int cautbin2(int val, int n){
int pos = 0;
for(int a = (1 << 20); a > 0; a /= 2)
    if(pos + a <= n && v[pos + a] <= val)
        pos += a;
        while(v[pos] == val)
        {
            pos--;
        }
        pos++;
        return pos;
}


int main()
{
    int n, m, dr, st, i, a, b;
    in >> n;
    for(i = 1; i <= n; i++)
    in >> v[i];
    in >> m;
    for(i = 1; i <= m; i++){
        in >> a >> b;
    if(a == 0)
        out << cautbin(b, n) << '\n';
    else if(a == 1)
        out << cautbin1(b, n) << '\n';
    else out << cautbin2(b, n) << '\n';
    }

    return 0;
}