#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.in");
int n,m,v[100005];
void bin1(int nr)
{
    int lb=1,ub=n;
    if(v[n]<nr||v[1]>nr){g<<-1<<'\n';return;}
    while(lb+1<ub)
    {
        int med=(lb+ub)/2;
        if(v[med]<=nr)lb=med;
        else ub=med;
    }
    g<<lb<<'\n';
}
void bin2(int nr)
{
    int lb=1,ub=n;
    while(lb+1<ub)
    {
        int med=(lb+ub)/2;
        if(v[med]<=nr)lb=med;
        else ub=med;
    }
    g<<lb<<'\n';
}
void bin3(int nr)
{
    int lb=1,ub=n;
    while(lb+1<ub)
    {
        int med=(lb+ub)/2;
        if(v[med]>=nr)ub=med;
        else lb=med;
    }
    g<<ub<<'\n';
}
int main()
{
    f>>n;
    for(int i=1;i<=n;i++)f>>v[i];
    f>>m;
    for(int i=1;i<=m;i++)
    {
        int val,en;
        f>>en>>val;
        switch(en)
        {
            case 0 : bin1(val);break;
            case 1 : bin2(val);break;
            case 2 : bin3(val);break;
        }
    }
    return 0;
}