同NOIP2004合唱队形，原题DP部分可以直接贴。
题意：求一个最长严格先上升后下降子序列，有两问，输出字典序最小解和字典序最大解。
从后往前DP，使用线段树维护，过程中使用后继数组记录转移过程。然后顺着模拟一遍取出来就行了。思路很简单。 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=300005;
long long A[MAXN];
struct tnode
{
    int dpval;
    int maxpos;
    int minpos;
    int l,r;
};
tnode operator + (const tnode &A,const tnode &B)
{
    tnode C;
    C.l=A.l;
    C.r=B.r;
    if(A.dpval>B.dpval)
    {
        C.dpval=A.dpval;
        C.maxpos=A.maxpos;
        C.minpos=A.minpos;
    }
    if(A.dpval<B.dpval)
    {
        C.dpval=B.dpval;
        C.maxpos=B.maxpos;
        C.minpos=B.minpos;
    }
    if(A.dpval==B.dpval)
    {
        C.dpval=A.dpval;
        C.maxpos=max(A.maxpos,B.maxpos);
        C.minpos=min(A.minpos,B.minpos);
    }
    return C;
}
struct Segment_Tree
{
    tnode t[4*MAXN];
    int id[MAXN];
    void update (int root)
    {
        int ch=root<<1;
        t[root]=t[ch]+t[ch+1];
    }
    void buildt(int root,int l,int r)
    {
        t[root].l=l;
        t[root].r=r;
        if(l!=r)
        {
            int mid=(l+r)>>1;
            int ch=root<<1;
            buildt(ch,l,mid);
            buildt(ch+1,mid+1,r);
            update(root);
        }
        else
        {
            t[root].dpval=t[root].maxpos=t[root].minpos=-1;
            id[l]=root;
        }
        return;
    }
    void change(int tvpos,int val,int pos)
    {
        int now=id[tvpos];
        if(t[now].dpval<val)
        {
            t[now].dpval=val;
            t[now].minpos=pos;
            t[now].maxpos=pos;
        }
        else if(t[now].dpval==val)
        {
            t[now].minpos=min(t[now].minpos,pos);
            t[now].maxpos=max(t[now].maxpos,pos);
        }
        else
        {
            return;
        }
        now>>=1;
        while(now)
        {
            update(now);
            now>>=1;
        }
        return;
    }
    tnode query(int root,int l,int r)
    {
        if(l>r)
        {
            tnode ret;
            ret.l=ret.r=ret.dpval=ret.maxpos=ret.minpos=-1;
            return ret;
        }
        if(t[root].l==l&&t[root].r==r)
        {
            return t[root];
        }
        int mid=(t[root].l+t[root].r)>>1;
        int ch=root<<1;
        if(r<=mid)return query(ch,l,r);
        else if(l>mid)return query(ch+1,l,r);
        else return query(ch,l,mid)+query(ch+1,mid+1,r);
    }
};
Segment_Tree ST0,ST1;
struct discretization_node
{
    int num;
    int ki;
}disc[MAXN];
bool cmp(discretization_node x,discretization_node y)
{
    return x.num<y.num;
}
int discretization(int a[],int n,discretization_node disc[])
{
    for(int i=1;i<=n;++i)
    {
        disc[i].num=a[i];
        disc[i].ki=i;
    }
    sort(disc+1,disc+1+n,cmp);
    int cnt=0,pre;
    for(int i=1;i<=n;++i)
    {
        if(i==1||a[disc[i].ki]!=pre)++cnt;
        pre=a[disc[i].ki];
        a[disc[i].ki]=cnt;
    }
    return cnt;
}
int n,a[MAXN],nextpos[MAXN][2][2],nextstate[MAXN][2][2],numsize,dp[MAXN][2],anslen,bg0,bg1,s0,s1;
vector<int>A1,A2;
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        anslen=0;
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&a[i]);
        }
        numsize=discretization(a,n,disc);
        ST0.buildt(1,1,numsize);
        ST1.buildt(1,1,numsize);
        for(int i=n;i;--i)
        {
            tnode temp1=ST1.query(1,1,a[i]-1);
            if(temp1.dpval!=-1)
            {
                dp[i][1]=temp1.dpval+1;

                nextstate[i][1][0]=1;
                nextpos[i][1][0]=temp1.minpos;

                nextstate[i][1][1]=1;
                nextpos[i][1][1]=temp1.maxpos;
            }
            else
            {
                dp[i][1]=1;

                nextstate[i][1][0]=-1;
                nextpos[i][1][0]=-1;

                nextstate[i][1][1]=-1;
                nextpos[i][1][1]=-1;

            }
            ST1.change(a[i],dp[i][1],i);
            tnode temp0=ST0.query(1,a[i]+1,numsize);
            if(temp1.dpval==-1&&temp0.dpval==-1)
            {
                dp[i][0]=1;

                nextstate[i][0][0]=-1;
                nextpos[i][0][0]=-1;

                nextstate[i][0][1]=-1;
                nextpos[i][0][1]=-1;

                ST0.change(a[i],dp[i][0],i);

                continue;
            }
            if(temp1.dpval>temp0.dpval)
            {
                dp[i][0]=temp1.dpval+1;

                nextstate[i][0][0]=1;
                nextpos[i][0][0]=temp1.minpos;

                nextstate[i][0][1]=1;
                nextpos[i][0][1]=temp1.maxpos;
            }
            else if(temp1.dpval<temp0.dpval)
            {
                dp[i][0]=temp0.dpval+1;

                nextstate[i][0][0]=0;
                nextpos[i][0][0]=temp0.minpos;

                nextstate[i][0][1]=0;
                nextpos[i][0][1]=temp0.maxpos;
            }
            else
            {
                dp[i][0]=temp0.dpval+1;
                if(temp1.minpos<=temp0.minpos)
                {
                    nextstate[i][0][0]=1;
                    nextpos[i][0][0]=temp1.minpos;
                }
                else
                {
                    nextstate[i][0][0]=0;
                    nextpos[i][0][0]=temp0.minpos;
                }
                if(temp0.maxpos>=temp1.maxpos)
                {
                    nextstate[i][0][1]=0;
                    nextpos[i][0][1]=temp0.maxpos;
                }
                else
                {
                    nextstate[i][0][1]=1;
                    nextpos[i][0][1]=temp1.maxpos;
                }
            }
            ST0.change(a[i],dp[i][0],i);
        }
        for(int i=1;i<=n;++i)
        {
            anslen=max(anslen,dp[i][0]);
        }
        bg0=bg1=-1;
        s0=s1=0;
        for(int i=1;i<=n;++i)
        {
            if(dp[i][0]==anslen)
            {
                if(bg0==-1||bg0>i)bg0=i;
                if(bg1==-1||bg1<i)bg1=i;
            }
        }
        A1.clear();
        A2.clear();
        while(s0!=-1)
        {
            A1.push_back(bg0);
            int ts=nextstate[bg0][s0][0];
            int tbg=nextpos[bg0][s0][0];
            bg0=tbg;
            s0=ts;
        }
        while(s1!=-1)
        {
            A2.push_back(bg1);
            int ts=nextstate[bg1][s1][1];
            int tbg=nextpos[bg1][s1][1];
            bg1=tbg;
            s1=ts;
        }
        for(int i=0;i<A1.size();++i)
        {
            printf("%d%c",A1[i],i==A1.size()-1?'\n':' ');
        }
        for(int i=0;i<A2.size();++i)
        {
            printf("%d%c",A2[i],i==A2.size()-1?'\n':' ');
        }
    }
    return 0;
}