#include <bits/stdc++.h>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");

int N,x,y;
int v[100001];
int M;


int Binara0(int left, int right, int x){

    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if(v[mid] <= x)
            left = mid + 1;
                else
                    right = mid - 1;
    }

    mid = (left + right) / 2;

    if(v[mid] > x)
        mid--;
    if(v[mid] == x)
        return mid;
    return -1;

}

int Binara1(int left, int right, int x){

    int mid;
    while (left < right) {
        mid = (left + right) / 2;
        if(v[mid] <= x)
            left = mid + 1;
                else
                    right = mid;
    }

    mid = (left + right) / 2;

    if(v[mid] > x)
        mid--;

    return mid;

}

int Binara2(int left, int right, int x){

    int mid;
    while (left < right) {
        mid = (left + right) / 2;
        if(v[mid] < x)
            left = mid + 1;
                else
                    right = mid;
    }

    mid = (left + right) / 2;

    if(v[mid] < x)
        mid++;

    return mid;

}



void Read(){

    in >> N;
    for(int i = 1; i <= N; ++i)
        in >> v[i];
    in >> M;
    for(int i = 1; i <= M; ++i){
        in >> x >> y;
        if(x == 0)out << Binara0(1,N,y) << '\n';
        if(x == 1)out << Binara1(1,N,y) << '\n';
        if(x == 2)out << Binara2(1,N,y) << '\n';
    }
}
int main(){

    Read();
    out.close();
    return 0;
}