#include<iostream>
#include<fstream>
using namespace std;
int cautbin0(int x,int v[],int n)
{
    int lst=1,ldr=n,mij,max=0;
    bool ok=0;
    while(lst<=ldr)
    {
        mij=(lst+ldr)/2;
        if(x==v[mij])
        {
            ok=1;
            if(mij>max)
            {
                max=mij;
                lst=mij+1;
            }
            else
            break;
        }
        else
        if(x<v[mij])
        ldr=mij-1;
        else
        if(x>v[mij])
        lst=mij+1;
    }
    if(ok)
    return max;
    else
    return 0;
}
int cautbin1(int x,int v[],int n)
{
    int lst=1,ldr=n,mij,max=0;
    while(lst<=ldr)
    {
        mij=(lst+ldr)/2;
        if(x>=v[mij])
        {
            if(mij>max)
            {
                max=mij;
                lst=mij+1;
            }
            else
            break;
        }
        else
        ldr=mij-1;
    }
    return max;
}
int cautbin2(int x,int v[],int n)
{
    int lst=1,ldr=n,mij,min=100000;
    while(lst<=ldr)
    {
        mij=(lst+ldr)/2;
        if(x<=v[mij])
        {
            if(mij<min)
            {
                min=mij;
                ldr=mij-1;
            }
            else
            break;
        }
        else
        lst=mij+1;
    }
    return min;
}
int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    int v[100001],m,n,i,x,opt;
    f>>n;
    for(i=1;i<=n;i++)
    f>>v[i];
    f>>m;
    for(i=1;i<=m;i++)
    {
        f>>opt>>x;
        switch(opt)
        {
            case 0:
            {
                if(cautbin0(x,v,n)!=0)
                g<<cautbin0(x,v,n)<<'\n';
                else
                g<<"-1\n";
                break;
            }
            case 1:
            {
                g<<cautbin1(x,v,n)<<'\n';
                break;
            }
            case 2:
            {
                g<<cautbin2(x,v,n)<<'\n';
                break;
            }
        }
    }
    f.close();
    g.close();
    return 0;
}