#include<fstream>
#define nmax 100002
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n, v[nmax], k;
int bs0(int x)
{
    int p = 1, u = n;
    int m;
    while(p <= u )
    {
        int m = (p + u)/2;
        if(v[m] <= x)

            p = m + 1;


       else

            u = m - 1 ;

    }
    m = (p + u) /2;
    if(v[m] > x)
    --m;
    if(v[m] == x)
        return m;
    return -1;
}
int bs1(int x)
{
    int p =1 , u = n;
    int m;
    while(p < u)
    {
       int m = (p + u) /2;
        if(v[m] <= x)

            p = m + 1 ;
        else
            u = m ;

    }
    m = (p + u )/2;
    if(v[m] > x)
        --m;
    return m;

}
int bs2(int x)
{
    int  u = n , p =1;
    int m;
    while(p < u)
    {
        int m = (p + u )/2 ;
        if(v[m] < x)
            p = m + 1;
                else
            u = m ;
    }
    m =(p + u)/2;
    if(v[m] < x)
        ++m;
     return m;

}
void read()
{
    int T, x, i ;
    fin >> n;
    for( i = 1 ; i <= n; i++)
        fin >> v[i];
    fin >> k;
    for( i = 1; i <= k ;i ++)
    {
        fin >>T >> x;
        if( T == 0 )
         {
             fout << bs0(x) <<'\n';
             continue;
         }
         if(T == 1)
         {
             fout << bs1(x)<<'\n';
         }
         if(T == 2)
         fout << bs2(x)<<'\n';
    }

}
int main()
{
    read();
    fin.close();
    fout.close();
    return 0;
}