#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int Binara0(int v[], int n, int val)
{
    int st, dr, poz=-2;
    st = 0;
    dr = n-1;
    while(st <= dr)
    {
        int mij = (st+dr)/2;
        if(v[mij] == val)
        {
            poz = mij;
            st = mij + 1;
        }
        else if(v[mij] < val)
            st = mij + 1;
        else
            dr = mij-1;

    }
    return poz+1;
}
int Binara1(int v[], int n, int val)
{
    int st, dr, poz;
    st = 0;
    dr = n-1;
    while(st <= dr)
    {
        int mij=(st+dr)/2;
        if(v[mij]<=val)
        {
            poz = mij;
            st = mij + 1;
        }
        else
            dr = mij - 1;
    }
    return poz+1;
}
int Binara2(int v[], int n, int val)
{
    int st, dr, poz;
    st = 0;
    dr = n-1;
    while(st <= dr)
    {
        int mij=(st+dr)/2;
        if(v[mij]>=val)
        {
            poz = mij;
            dr = mij - 1;
        }
        else
            st = mij + 1;
    }
    return poz+1;
}
int main()
{
    int n, m, x, t;
    fin >> n;
    int v[100000];
    for(int i=0; i < n; i++)
        fin >> v[i];
    fin >> m;
    for(int i=0; i < m; i++)
    {
        fin >> t >> x;
        if(t==0)
            fout << Binara0(v, n, x) << "\n";
        else if(t==1)
            fout << Binara1(v, n, x) << "\n";
        else
            fout << Binara2(v, n, x) << "\n";
    }
    return 0;
}