#include<fstream>
using namespace std;
 
#define MAX 100010
 
int N,M,v[MAX];
 
 
ifstream in("cautbin.in");
ofstream out("cautbin.out");
 
int inline max(int e1,int e2)
{
    if(e1>e2)
        return e1;
    return e2;
}
int inline min(int e1,int e2)
{
    if(e1<e2)
        return e1;
    return e2;
}
 
void operatie(int op,int el)
{
    int st=1,ul=N,mid,m=-1;
    if(op==0)
    {
        while(st<=ul)
        {
            mid=(ul+st)/2;
            if(v[mid]==el)
            {
                m=max(mid,m);
                st=mid+1;
            }
            else if(v[mid]<el)
              st=mid+1;
            else
              ul=mid-1;
        }
        out<<m<<'\n';
    }
 
    else if(op==1)
    {
        while(st<=ul)
        {
            mid=(ul+st)/2;
            if(v[mid]<=el)
            {
                m=max(mid,m);
                st=mid+1;
            }
            else
              ul=mid-1;
        }
        out<<m<<'\n';
    }
    else if(op==2)
    {
        m=(1<<30);
        while(st<=ul)
        {
            mid=(ul+st)/2;
            if(v[mid]>=el)
            {
                m=min(mid,m);
                ul=mid-1;
            }
            else
              st=mid+1;
         
        }
        out<<m<<'\n';
    }
}
 
int main()
{
    in>>N;
    for(int i=1;i<=N;i++)
        in>>v[i];
 
    in>>M;
    int op,nr;
    for(int i=1;i<=M;i++)
    {
        in>>op>>nr;
        operatie(op,nr);
    }
    in.close();
    out.close();
    return 0;
}