#include <iostream>
#include <fstream>
#define N 100010

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int v[N],i,j,n,m,x,y;
int bcaut1(int s,int d,int p,int val)
{
    if(s<=d){
        int mij=(s+d)/2;
        if(v[mij]==val)
        {
            bcaut1(mij+1,d,mij,val);
        }
        else
        {
            if(v[mij]>val)
                bcaut1(s,mij-1,p,val);
            else
                bcaut1(mij+1,d,p,val);
        }
    }
    else
    {
        return p;
    }
}
int bcaut2(int s,int d,int p,int val)
{
    if(s<=d)
    {
        int mij=(s+d)/2;
        if(v[mij]<=val)
            bcaut2(mij+1,d,mij,val);
        else
        {
                bcaut2(s,mij-1,p,val);
        }
    }
    else
    {
        return p;
    }
}
int bcaut3(int s,int d,int p,int val)
{
    if(s<=d)
    {
        int mij=(s+d)/2;
        if(v[mij]>=val)
            bcaut3(s,mij-1,mij,val);
        else
            bcaut3(mij+1,d,p,val);
    }
    else
    {
        return p;
    }
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    f>>m;
    while(m!=0)
    {
        f>>x>>y;
        if(x==0)
            g<<bcaut1(1,n,-1,y)<<"\n";
        else
            if(x==1)
            g<<bcaut2(1,n,-1,y)<<"\n";
            else
                if(x==2)
                g<<bcaut3(1,n,-1,y)<<"\n";
        m--;
    }
}