#include <fstream>
#include <algorithm>
using namespace std;
int v[100002];
int n,m,i,s,d,p,xx,mij,c;
int cerinta_1(int x)
{
    s=1;
    d=n;
    p=-1;
    while(s<=d)
    {
        mij=s+(d-s)/2;
        if(v[mij]==x)
            p=mij;
        if(v[mij]<=x)
            s=mij+1;
        else
            d=mij-1;
    }
    return p;
}
int cerinta_2(int x)
{
    s=1;
    d=n;
    p=-1;
    while(s<=d)
    {
        mij=s+(d-s)/2;
        if(v[mij]<=x)
        {
            p=mij;
            s=mij+1;
        }
        else
            d=mij-1;
    }
    return p;
}
int cerinta_3(int x)
{
    s=1;
    d=n;
    p=-1;
    while(s<=d)
    {
        mij=s+(d-s)/2;
        if(v[mij]>=x)
        {
            p=mij;
            d=mij-1;
        }
        else
            s=mij+1;
    }
    return p;
}
int main()
{
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");
    in>>n;
    for(i=1;i<=n;i++)
    {
        in>>v[i];
    }
    in>>m;
    for(i=1;i<=m;i++)
    {
        in>>c>>xx;
        if(c==0)
            out<<cerinta_1(xx)<<endl;
        if(c==1)
            out<<cerinta_2(xx)<<endl;
        if(c==2)
            out<<cerinta_3(xx)<<endl;
    }
    return 0;
}