题面传送门

原题题号：Codeforces Gym 101821B

题意：

给出一个排列 \(p\)，要你找出一个最长上升子序列（LIS）和一个最长下降子序列（LDS），满足它们没有公共元素。或告知无解。

\(1 \leq n \leq 5 \times 10^5\)。

wxh 太强辣！wxhtxdy！

首先可以发现一个小性质，那就是原序列任意一个 LIS 和 LDS 至多只有 \(1\) 个公共元素。

假设它们有 \(2\) 个公共元素 \(p_i,p_j(ip_j\)，矛盾！

我们预处理出 \(f_i\) 表示包含 \(p_i\) 的 LDS 个数，\(sum\) 表示总的 LDS 个数。由于这些数可能很大，我们可以将它模上一个比较大的数。

由于我们只需构造出一组合法的解，我们的目标就是检验是否存在一个合法的 LIS，然后顺带着找出原序列扣除掉这个 LIS 后得到的序列 \(p'\) 的一个 LDS。

我们考虑不合法的 LIS 长啥样，假设这个 LIS 为 \([a_{x_1},a_{x_2},\dots,a_{x_l}]\)，因为它不合法，所以不存在与它没有交集的 LDS，也就是所有 LDS 都与它有交集。

而根据之前的性质一个 LIS 和 LDS 至多只有 \(1\) 个公共元素，故 \(f_{x_1}+f_{x_2}+\dots+f_{x_l}=sum\)。

那么怎样找这样一个 LIS 呢？

先用树状数组求出 LIS、LDS 的长度，以及上文提到的 \(f_i,sum\) 的值。

求 LIS 的时候结构体里另外维护四个值 \(m_1,m_2,p_1,p_2\)，表示在满足上升子序列的长度最大的情况下，两个不同的 \(f_{x_1}+f_{x_2}+\dots+f_{x_l}\) 的值，以及它们对应的前驱。

如果发现存在一个 LIS 它的 \(f_{x_1}+f_{x_2}+\dots+f_{x_l} \neq sum\)，那么直接跳出输出就可以了。

/*
Contest: -
Problem: Codeforces Gym 101821 B
Author: tzc_wk
Time: 2020.10.4
*/
#include <bits/stdc++.h>
using namespace std;
#define fi            first
#define se            second
#define pb            push_back
#define fz(i,a,b)    for(int i=a;i<=b;i++)
#define fd(i,a,b)    for(int i=a;i>=b;i--)
#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define all(a)        a.begin(),a.end()
#define fill0(a)    memset(a,0,sizeof(a))
#define fill1(a)    memset(a,-1,sizeof(a))
#define fillbig(a)    memset(a,0x3f,sizeof(a))
#define y1            y1010101010101
#define y0            y0101010101010
typedef pair<int,int> pii;
typedef long long ll;
inline int read(){
    int x=0,neg=1;char c=getchar();
    while(!isdigit(c)){
        if(c=='-') neg=-1;
        c=getchar();
    }
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    return x*neg;
}
const int MOD=23895631;
inline void add(int &x,int v){
    x+=v;if(x>=MOD) x-=MOD;
}
struct numway{
    int val,way;
    numway(int _val=0,int _way=0){val=_val;way=_way;}
    numway operator +(numway x){
        numway z=*this;
        if(x.val>z.val) z.val=x.val,z.way=0;
        if(x.val==z.val) z.way=(z.way+x.way)%MOD;
        return z;
    }
};
int n=read(),a[500005];
struct bit1{
    numway tr[500005];
    inline void clear(){
        for(int i=1;i<=n;i++)
            tr[i].val=tr[i].way=0;
    }
    inline void modify(int x,numway y){
        for(int i=x;i<=n;i+=(i&(-i)))
            tr[i]=tr[i]+y;
    }
    inline numway query(int x){
        numway ans(0,1);
        for(int i=x;i;i-=(i&(-i)))
            ans=ans+tr[i];
        return ans;
    }
} b1;
struct bit2{
    int tr[500005];
    inline void clear(){
        fill0(tr);
    }
    inline void modify(int x,int y){
        for(int i=x;i<=n;i+=(i&(-i)))
            tr[i]=max(tr[i],y);
    }
    inline int query(int x){
        int ans=0;
        for(int i=x;i;i-=(i&(-i)))
            ans=max(ans,tr[i]);
        return ans;
    }
} b2;
int lds_len=0,lis_len=0;
numway lds1[500005],lds2[500005];
int f[500005];
struct event{
    int val,m1,m2,p1,p2;
    event(int _val=0,int _m1=-1,int _m2=-1,int _p1=0,int _p2=0){
        val=_val;m1=_m1;m2=_m2;p1=_p1;p2=_p2;
    }
    friend event operator +(event a,event b){
        if(a.val>b.val) return a;
        if(a.val<b.val) return b;
        if(a.m1==-1) return b;
        else if(a.m2==-1){
            if(b.m1==-1||b.m1==a.m1) a.m2=b.m2,a.p2=b.p2;
            else a.m2=b.m1,a.p2=b.p1;
            return a;
        }
        else return a;
    }
};
struct bit3{
    event tr[500005];
    inline void modify(int x,event v){
        for(int i=x;i<=n;i+=(i&(-i)))
            tr[i]=tr[i]+v;
    }
    inline event query(int x){
        event ans(0,0,-1,0,0);
        for(int i=x;i;i-=(i&(-i)))
            ans=ans+tr[i];
        return ans;
    }
} b3;
event lis[500005];
vector<int> ans_lis,ans_lds;
bool cant[500005];
struct bit4{
    pii tr[500005];
    inline void modify(int x,pii v){
        for(int i=x;i<=n;i+=(i&(-i)))
            tr[i]=max(tr[i],v);
    }
    inline pii query(int x){
        pii ans=make_pair(0,0);
        for(int i=x;i;i-=(i&(-i)))
            ans=max(ans,tr[i]);
        return ans;
    }
} b4;
pii lls[500005];
inline void dump(int x,int y){
    while(x){
        ans_lis.pb(x);cant[x]=1;
        if(lis[x].m1==y){y=(y-f[x]+MOD)%MOD;x=lis[x].p1;}
        else{y=(y-f[x]+MOD)%MOD;x=lis[x].p2;}
    }
    reverse(all(ans_lis));
    printf("%d\n",lis_len);
    foreach(it,ans_lis) printf("%d ",*it);printf("\n");
    for(int i=n;i>=1;i--){
        if(cant[i]) continue;
        lls[i]=b4.query(a[i]-1);
        lls[i].fi++;
        b4.modify(a[i],make_pair(lls[i].fi,i));
    }
    for(int i=1;i<=n;i++){
        if(lls[i].fi==lds_len){
            for(int j=i;j;j=lls[j].se){
                ans_lds.pb(j);
            }
            break;
        }
    }
    printf("%d\n",lds_len);
    foreach(it,ans_lds) printf("%d ",*it);printf("\n");
}
int main(){
    for(int i=1;i<=n;i++) a[i]=read();
    b1.clear();
    for(int i=1;i<=n;i++){
        lds1[i]=b1.query(n-a[i]);lds1[i].val++;
        b1.modify(n-a[i]+1,lds1[i]);lds_len=max(lds1[i].val,lds_len);
    }
    b1.clear();
    for(int i=n;i>=1;i--){
        lds2[i]=b1.query(a[i]-1);lds2[i].val++;
        b1.modify(a[i],lds2[i]);
    }
//    for(int i=1;i<=n;i++) printf("%d %d %d %d\n",lds1[i].val,lds1[i].way,lds2[i].val,lds2[i].way);
    for(int i=1;i<=n;i++){
        if(lds1[i].val+lds2[i].val-1==lds_len){
            f[i]=1ll*lds1[i].way*lds2[i].way%MOD;
        }
//        cout<<f[i]<<endl;
    }
    int sum=0;
    for(int i=1;i<=n;i++){
        if(lds1[i].val==lds_len)
            sum=(sum+lds1[i].way)%MOD;
    }
//    cout<<sum<<endl;
    for(int i=1;i<=n;i++){
        int x=b2.query(a[i]-1);
        b2.modify(a[i],x+1);
        lis_len=max(lis_len,x+1);
    }
    for(int i=1;i<=n;i++){
        lis[i]=b3.query(a[i]-1);
        lis[i].val++;
        if(lis[i].m1!=-1){
            lis[i].m1=(lis[i].m1+f[i])%MOD;
        }
        if(lis[i].m2!=-1){
            lis[i].m2=(lis[i].m2+f[i])%MOD;
        }
//        printf("%d %d %d %d %d\n",lis[i].val,lis[i].m1,lis[i].m2,lis[i].p1,lis[i].p2);
        if(lis[i].val==lis_len){
            if(lis[i].m1!=-1&&lis[i].m1!=sum){
                dump(i,lis[i].m1);return 0;
            }
            if(lis[i].m2!=-1&&lis[i].m2!=sum){
                dump(i,lis[i].m2);return 0;
            }
        }
        b3.modify(a[i],event(lis[i].val,lis[i].m1,lis[i].m2,(lis[i].m1!=-1)?(i):(0),(lis[i].m2!=-1)?(i):(0)));
    }
    printf("IMPOSSIBLE\n");
    return 0;
}