#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
std::ifstream in("cautbin.in");
std::ofstream out("cautbin.out");

const int MAXN= 100003, MAXM = 100003;
int n,m;
int *v;
// cea mai mare val unde se afla x sau -1 daca nu exista

int bs0(int lt, int rt, int x)
{
    int mid;
    while( (rt - lt)>1)
    {
        mid = lt +(rt-lt)/2;
        if(x >= v[mid])
            lt = mid;
        else
            rt = mid-1;
    }
    if( v[lt] !=x && v[rt]!=x)
        return -1;
    if(v[lt+1] == x)
        lt++;
    return lt;
}
// cea mai mare poz unde se afla un element <=x ( garantat exista)
int bs1(int lt, int rt, int x)
{
    int mid;
    while( (rt - lt)>1)
    {
        mid = lt +(rt-lt)/2;
       if ( v[mid] <= x)
            lt = mid;
       else
            rt = mid-1;
    }
    if(v[lt+1]<=x)
        lt++;
    return lt;
}
//cea mai mic pozitie unde e un el cu val <= x(exita garantat)
int bs2(int lt, int rt, int x)
{
    int mid;
    while( (rt - lt)>1)
    {
        mid = lt +(rt-lt)/2;
        if( v[mid] >= x)
            rt = mid;
        else
            lt = mid+1;
    }
    if (v[lt]<x)
        lt++;
    return lt;
}
int main()
{

    in >> n;
    v = new int[n+1];
    for(int i = 1 ; i <= n ; i ++)
        in >> v[i];
    in >> m;
    int operatie,x;
    int res;
    for(int i = 0 ; i < m ; i++)
    {
        in >> operatie>> x;

        switch(operatie)
        {
            case 0: out<<bs0(1,n,x)<<'\n'; break;
            case 1: out<<bs1(1,n,x)<<'\n'; break;
            case 2: out<<bs2(1,n,x)<<'\n'; break;
        }
    }

    return 0;
}