#include<fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[100001];
int i, n, m, tip, val;
inline int caut0 (int key) 
{   int m,u=n,p=1;
    while (p <= u) 
	{   m = (p + u) / 2;
        if (v[m] <= key)
            p = m + 1;
        else
            u = m - 1;
    }
    m = (p + u) / 2;
    if (v[m] > key) 
		m --;
    if (v[m] == key)
        return m;
    return -1;
}

int caut1(int key)
{int m,u=n,p=1;
    while (p < u)
	{   m = (p + u) / 2;
        if (v[m] <= key)
            p = m + 1;
        else
            u = m;
    }
    m = (p + u) / 2;
    if (v[m] > key)
       -- m;
    return m;
}

int caut2(int key)
{int m,p=1,u=n;
    while (p < u)
	{   m = (p + u) / 2;
        if (v[m] < key)
            p = m + 1;
        else
            u = m;
    }
    m = (p + u) / 2;
    if (v[m] < key)
       ++ m;
    return m;
}

int main () 
{   fin >> n;
    for (i=1;i<=n;++i)
       fin >> v[i];
    fin >> m;
    for (i=1;i<=m;++i)
	{   fin >> tip >> val;
		if (tip == 0)
			fout << caut0(val) << '\n';
		if (tip == 1)
			fout << caut1(val) << '\n';
		if (tip == 2)
			fout << caut2(val) << '\n';
    }
    return 0;
}