#include <fstream>

using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");
int q,s,cautat,a[100001],x,n,t,y,m;

int cautbin0()
{
    q=1;
    s=n;
    while(q<=s)
    {
        cautat=q+(s-q)/2;
        if(a[cautat]<=x) q=cautat+1;
        else s=cautat-1;
    }
    if(a[s]==x) return s;
    return -1;
}
int cautbin1()
{
    q=1;
    s=n;
    while(q<=s)
    {
        cautat=q+(s-q)/2;
        if(a[cautat]<=x) q=cautat+1;
        else s=cautat-1;
    }
    return s;
}
int cautbin2()
{
    q=1;
    s=n;
    while(q<=s)
    {
        cautat=q+(s-q)/2;
        if(a[cautat]>=x) s=cautat-1;
        else q=cautat+1;
    }
    return q;
}

int main()
{
    in>>n;
    for(int i=1; i<=n; i++)
        in>>a[i];
    in>>m;
    for(int i=1; i<=m; i++)
    {
        in>>y>>x;
        if(y==0) out<<cautbin0()<<endl;
        if(y==1) out<<cautbin1()<<endl;
        if(y==2) out<<cautbin2()<<endl;
    }
    return 0;
}