#include <iostream>
#include <fstream>

using namespace std;

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

const int L = 16;

int n,v[100001];

int a(int x){
    int r = 0;
    int pas = 1 << L;
    while(pas != 0){
        if(r + pas <= n && v[r + pas] <= x)
            r += pas;
        pas /= 2;
    }
    if(v[r] != x)
        r = -1;
    return r;
}

int c(int x){
    int r = 0;
    int pas = 1 << L;
    while(pas != 0){
        if(r + pas <= n && !(v[r + pas] >= x))
            r += pas;
        pas /= 2;
    }
    r++;
    return r;
}
int b(int x){
    int r = 0;
    int pas = 1 << L;
    while(pas != 0){
        if(r + pas <= n && v[r + pas] <= x)
            r += pas;
        pas /= 2;
    }
    return r;
}

int main()
{
    int m,i,d,k;
    in >> n;
    for(i = 1;i <= n; i++)
        in >> v[i];
    in >> m;
    for(i = 1;i <= m; i++){
        in >> d >> k;
        if(d == 0)
            out << a(k);
        if(d == 1)
            out << b(k);
        if(d == 2)
            out << c(k);
        out << "\n";
    }
    return 0;
}