#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int a[100010],n;
int op0(int x),op1(int x),op2(int x);
int main()
{
    int m,i,x,op;
    fin>>n;
     for(i=1;i<=n;i++)
        fin>>a[i];
    fin>>m;
    for(i=1;i<=m;i++)
    {
        fin>>op>>x;
        if(!op)
            fout<<op0(x)<<"\n";
        else
            if(op==1)
            fout<<op1(x)<<"\n";
            else
                fout<<op2(x)<<"\n";
    }
    return 0;
}
int op0(int x)
{
    int mij,st=0,dr;
    dr=n+1;
    while(dr-st>1)
    {
        mij=(st+dr)/2;
        if(a[mij]<=x)
            st=mij;
        else
            dr=mij;
    }
    if(a[st]==x)
        return st;
    else
        return -1;
}
int op1(int x)
{
    int mij,st=0,dr;
    dr=n+1;
    while(dr-st>1)
    {
        mij=(st+dr)/2;
        if(x>=a[mij])
            st=mij;
        else
            dr=mij;
    }
    return st;
}
int op2(int x)
{
    int mij,st=0,dr;
    dr=n+1;
    while(dr-st>1)
    {
        mij=(st+dr)/2;
        if(a[mij]>=x)
            dr=mij;
        else
            st=mij;
    }
    return dr;

}