#include <bits/stdc++.h>

using namespace std;

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

const int NMax = 100001;

int a[NMax], b[NMax];
int n, x, v, m;

int nr0(int n, int a[], int v)
{
    int i, j;
    i = 1; j = n;
    int mijl;

    while(i <= j)
    {
        mijl = (i + j) / 2;

        if(a[mijl] <= v) i = mijl + 1;
        else j = mijl - 1;
    }
    mijl = (i + j) / 2;
    if(a[mijl] == v) return mijl;
    if(v > a[mijl]) m--;
    return -1;
}

int nr1(int n, int a[], int v)
{
    int i, j;
    i = 1; j = n;
    int mijl;

    while(i <= j)
    {
        mijl = (i + j) / 2;

        if(a[mijl] <= v) i = mijl + 1;
        else j = mijl - 1;
    }
    mijl = (i + j) / 2;
    if(a[mijl] <= v) return mijl;
    if(a[mijl] > v) mijl--;
    return mijl;
}
int nr2(int n, int a[], int v)
{
    int i, j;
    i = 1; j = n;
    int mijl;

    while(i <= j)
    {
        mijl = (i + j) / 2;

        if(a[mijl] >= v) j = mijl - 1;
        else i = mijl + 1;
    }
    mijl = (i + j) / 2;
    if(a[mijl] >= v) return mijl;
    if(a[mijl] < v) mijl++;
    return mijl;
}
int main()
{
    f >> n;
    for(int i = 1; i <= n; ++i)
        f >> a[i];
    f >> m;
    for(int i = 1; i <= m; ++i)
    {
        f >> x;
        f >> v;
        if(x == 0) g << nr0(n, a, v) << '\n';
        if(x == 1) g << nr1(n, a, v) << '\n';
        if(x == 2) g << nr2(n, a, v) << '\n';
    }
}