#include <iostream>
#include <fstream>

using namespace std;

unsigned int a[100005],n;

int cerinta1(const unsigned int x)
{
    int st=1,dr=n;
    while (st<=dr)
    {
        int mij=(st+dr)/2;
        if (x>=a[mij])
            st=mij+1;
        else
            dr=mij-1;
    }
    int mij=(st+dr)/2;
    if (a[mij]==x)
        return mij;
    else if (a[--mij]==x)
        return mij;
    return -1;
}

int cerinta2(const unsigned int x)
{
    int st=1,dr=n;
    while (st<=dr)
    {
        int mij=(st+dr)/2;
        if (x>=a[mij])
            st=mij+1;
        else
            dr=mij-1;
    }
    int mij=(st+dr)/2;
    if (a[mij]<=x)
        return mij;
    else if (a[--mij]<=x)
        return mij;
    return 1;
}

int cerinta3(const unsigned int x)
{
    int st=1,dr=n;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if (x<=a[mij])
            dr=mij-1;
        else
            st=mij+1;
    }
    int mij=(st+dr)/2;
    if (a[mij]>=x)
        return mij;
    else if (a[++mij]>=x)
        return mij;
    return n;
}

int main()
{
    ifstream fin ("cautbin.in");
    ofstream fout ("cautbin.out");
    int m;
    fin>>n;
    for (unsigned int i=1;i<=n;i++)
        fin>>a[i];
    fin>>m;
    for (;m;m--)
    {
        char c;
        unsigned int x;
        fin>>c>>x;
        switch(c)
        {
            case '0':
            {
                fout<<cerinta1(x)<<'\n';
                break;
            }
            case '1':
            {
                fout<<cerinta2(x)<<'\n';
                break;
            }
            case '2':
            {
                fout<<cerinta3(x)<<'\n';
                break;
            }
        }
    }
    return 0;
}