#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>>1)
        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>>1)
        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>>1)
        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;
}