#include <iostream>
#include <fstream>
using namespace std;
int n,m,v[100003];
int mij;
int binary0(int x)//cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca nu se gaseste
{
    int lo = 1, hi = n;
    while( hi - lo > 1)
    {
         mij = (lo+hi)/2;
         if ( v[ mij ] <= x)
            lo = mij;
         else
            hi = mij-1;
    }
    if (v[ lo ] == x)
        return lo;
    lo++;
    if( v[ lo ] == x )
        return lo;
    return -1;


}
int binary1(int x)//cea mai mare pozitie pe care se afla un element cu valoarea <= x
{

    int lo = 1, hi = n;
    while(  hi - lo >1)
    {
         mij = (lo+hi)/2;
         if ( v[ mij ] <= x )
            lo = mij;
         else
            hi = mij-1;
    }
    lo++;
    if( v[ lo ] <= x )
        return lo;
    lo--;
    if (v[lo] <=x )
        return lo;
    return -1;
}
int binary2(int x)//cea mai mica pozitie pe care se afla un element cu valoarea >=x
{
    int lo = 1, hi = n;
    while( hi - lo >1)
    {
         mij = (lo+hi)/2;
         if ( v[ mij ] < x )
            lo = mij+1;
         else
            hi = mij;
    }
    if( v[ lo ] >= x )
        return lo;
    lo++;
    if( v[ lo ] >= x )
        return lo;
    return -1;
}
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int main()
{
    in>> n;
    for(int i = 1 ; i <= n ; i++)
        in >> v[i];
    in >> m;
    int op,x;
    while( m> 0)
    {
        in >> op >> x;
        switch(op)
        {
            case 0 : out<<binary0(x)<<'\n'; break;
            case 1 : out<<binary1(x)<<'\n'; break;
            case 2 : out<<binary2(x)<<'\n'; break;
        }
        m--;
    }
    return 0;
}