#include <fstream>
using namespace std;
#define Nmax 100000

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n,v[Nmax],m;
int bsearch0 (int p, int u, int key) {

    int m;



    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 bsearch1 (int p, int u, int key) {

    int m, n = u;



    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 bsearch2 (int p, int u, int key) {

    int m;



    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(int i=1;i<=n;++i)
    {
        fin>>v[i];
    }
    fin>>m;
    for(int i=1;i<=m;++i)
    {
        int a,b;
        fin>>a>>b;
        if(a==0)
        {
           fout<<bsearch0(1,n,b)<<'\n';
        }
        else if(a==1)
        {
           fout<<bsearch1(1,n,b)<<'\n';
        }
        else
        {
            fout<<bsearch2(1,n,b)<<'\n';
        }
    }
    return 0;
}