#include <fstream>
using namespace std;

int v[100000 + 1], N, M, c, x;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int cautBinZero(int x){
    int left = 1, right = N;

    while(left <= right){
        int mid = (left + right)/2;

        if(v[mid] == x && (mid == N || v[mid + 1] > x)) return mid;

        if(v[mid] <= x) left = mid + 1;
        else right = mid - 1;
    }

    return - 1;
}

int cautBinOne(int x){
    int left = 1, right = N;

    while(left <= right){
        int mid = (left + right)/2;

        if(v[mid] <= x && (mid == N || v[mid + 1] > x )) return mid;

        if(v[mid + 1] <= x) left = mid + 1;
        else right = mid - 1;
    }
}

int cautBinTwo(int x){
    int left = 1, right = N;

    while(left <= right){
        int mid = (left + right)/2;

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

        if(v[mid - 1] >= x) right = mid - 1;
        else left = mid + 1;
    }
}
int main()
{
    fin>>N;
    for(int i = 1; i <= N; i++) fin>>v[i];

    fin>>M;

    for(int i = 1; i <= M; i++){
        fin>>c>>x;

        if(c == 1) fout << cautBinOne(x) << "\n";
        else if(c == 2) fout <<cautBinTwo(x) << "\n";
        else fout<<cautBinZero(x) << "\n";
    }
}