#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
using namespace std;
FILE *in = fopen("cautbin.in", "r"), *out = fopen("cautbin.out", "w");
int v[100001], n, m;

int cb0(int inf, int sup, int key)
{
    int m;
    while (inf <= sup){
        m = (sup +inf) / 2;
        if (v[m] == key) break;
        else if (v[m] < key)
            inf = m + 1;
        else if (v[m] > key)
            sup = m - 1;
    }

    if (inf > sup) return -1;
    else{
        while (key == v[m])
            m++;
        return m-1;
    }

}
int cb1(int inf, int sup, int key)
{

    int m,sol;
    while (inf <=sup){

        m = (sup +inf) / 2;
        if (v[m] <=key){
            sol=m;
            inf = m + 1;}
        else
            sup = m-1;
    }


    return sol;
}
int cb2(int inf, int sup, int key)
{
    int m,sol;
    while (inf <=sup){
        m = (sup +inf) / 2;
        if (v[m] < key)
            inf = m + 1;
        else{
          sol=m;
            sup = m-1;
        }
    }

    return sol;
}
int main()
{
    int i,val,tip;
    fscanf(in, "%d", &n);
    for (i = 1; i <= n; i++)
        fscanf(in, "%d", v + i);
    fscanf(in, "%d", &m);
    for (i = 0; i < m; i++){
        fscanf(in, "%d %d", &tip, &val);
        if (tip == 0) fprintf(out,"%d\n", cb0(1, n, val));
        else if (tip == 1) fprintf(out,"%d\n", cb1(1, n, val));
        else if (tip == 2) fprintf(out,"%d\n", cb2(1, n, val));
    }
    fclose(out);
    return 0;
}