#include <iostream>
#include <fstream>

using namespace std;
ifstream in ("cautbin.in");
ofstream out ("cautbin.out");

int v[100001];
int cbin0 (int val, int n)
{
int pos=0;

for (int msk=1<<20; msk>0; msk/=2)
	if (pos+msk<=n&& v[pos+msk]<= val)
	pos+=msk;
if (v[pos]==val) return pos;
else return -1;
}
int cbin1 (int val, int n)
{
int pos=0;

for (int msk=1<<20; msk>0; msk/=2)
	if (pos+msk<=n && v[pos+msk]<= val)
	pos+=msk;
    while (v[pos]>val)
    {
        pos--;
    }
    return pos;
}
int cbin2 (int val, int n)
{
int pos=0;

for (int msk=1<<20; msk>0; msk/=2)
	if (pos+msk<=n && v[pos+msk]<= val)
	pos+=msk;
    while (v[pos]==val)
    {
        pos--;
    }
     while (v[pos]<val)
    {
        pos++;
    }
    return pos;
}
int main()
{
    long long n,m, op, x, i;

    in>>n;
    for (i=1; i<=n; i++)
        {
            in>>v[i];
        }
        in>>m;

    for (i=1; i<=m; i++)
    {
        in>>op>>x;
        if (op==0)
        out<< cbin0 (x,n)<<endl;
        else if (op==1)
            out<<cbin1 (x,n)<<endl;
        else if (op==2)
            out<<cbin2 (x,n)<<endl;

    }



    return 0;
}