#include <iostream>
#include <cstdio>
using namespace std;
int v[100010],maxim=-1,maxim2,minim;
void c_bin0(int st,int dr,int x)
{
   if(st<dr)
    {
        int mid=(st+dr)/2;
        if(v[mid]==x)
            if(maxim<mid)
               {
                maxim=mid;
                c_bin0(mid+1,dr,x);
                }
            else
                if(x<v[mid])
                    c_bin0(st,mid-1,x);
                else
                    c_bin0(mid+1,dr,x);
    }
    else
        return ;
}
void c_bin1(int st,int dr,int x)
{
   if(st<dr)
    {
        int mid=(st+dr)/2;
        if(v[mid]<=x)
            if(maxim2<mid)
               {
                maxim2=mid;
                c_bin1(mid+1,dr,x);
                }
            else
                if(x<v[mid])
                    c_bin1(st,mid-1,x);
                else
                    c_bin1(mid+1,dr,x);
    }
    else
        return ;
}

void c_bin2(int st,int dr,int x)
{
   if(st<dr)
    {
        int mid=(st+dr)/2;
        if(v[mid]>=x)
            if(minim>mid)
               {
                minim=mid;
                c_bin2(st,mid-1,x);
                }
            else
                if(x<v[mid])
                    c_bin2(st,mid-1,x);
                else
                    c_bin2(mid+1,dr,x);
    }
    else
        return ;
}


int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);

    int i,n,m;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i];
        cin>>m;
    while(m--)
    {
        int x,querry;
        cin>>querry>>x;
        if(querry==0)
            {
                c_bin0(1,n,x);
                cout<<maxim<<"\n";
                maxim=-1;
            }
        else
            if(querry==1)
        {
            maxim2=-1;
            c_bin1(1,n,x);
            cout<<maxim2<<"\n";

        }
        else
        {
            minim=n;
            c_bin2(1,n,x);
            cout<<minim-1<<"\n";
        }


    }


    return 0;
}