#include <iostream>

#include <fstream>

using namespace std;

ifstream fin("cautbin.in");

ofstream fout("cautbin.out");

constexpr int NX = 100010;

int a[NX];

int binary0(int st, int dr, int val)

{

    int m;

    while(st<=dr)

    {



        m=st+(dr-st)/2;

        if(a[m]<=val)

            st=m+1;

        else

            dr=m-1;

    }

    m=st+(dr-st)/2;

    if(a[m]>val)

        m--;

    if(a[m]==val)

        return m;

    return -1;

}

int binary1(int st, int dr, int val)

{

    int m;

    while(st<dr)

    {

        m=st+(dr-st)/2;

        if(a[m] <= val)

            st=m+1;

        else

            dr=m;

    }

    m=st+(dr-st)/2;

    if(a[m]>val)

        --m;

        return m;

}

int binary2(int st, int dr, int val)

{

    int m;

    while(st<dr)

    {

        m=st+(dr-st)/2;

        if(a[m] < val)

            st=m+1;

        else

            dr=m;

    }

    m=st+(dr-st)/2;

    if(a[m]<val)

        m++;

        return m;

}

int main()

{

    int n, m;

    fin>>n;

    for(int i=0; i<n; ++i)

        fin>>a[i];

    fin>>m;

    unsigned int x, y;

    for(int i=0; i<m; ++i)

    {

        fin>>x>>y;

        switch(x)

        {

        case 0:

            fout<<binary0(0, n-1, y)+1<<"\n";

            break;

        case 1:

            fout<<binary1(0, n-1, y)+1<<"\n";

            break;

        case 2:

            fout<<binary2(0, n-1, y)+1<<"\n";

            break;

        }

    }

    return 0;

}