// uva 10534 Wavio Sequence

//

// 能够将题目转化为经典的LIS。

// 从左往右LIS记作d[i],从右往左LIS记作p[i];

// 则最后当中的min(d[i],p[i])就是这个波动序列的一半

// 在这最后的min(d[i],p[i]) * 2 + 1 的最大值就是我们所要求的答案

//

// 这题開始想的最后的答案是d[i]==p[i]的时候求最大。

// 可是这样是不正确的，比如n=4,

// 1,3,1,0

// 最长的应该是3，可是我的答案是1，明显是错的

//

// 细致想来，确实是这样。仅仅要取min(d[i],p[i])的最小值作为一半就能够了

//

// 还是欠缺考虑。继续练

#include <algorithm>

#include <bitset>

#include <cassert>

#include <cctype>

#include <cfloat>

#include <climits>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <functional>

#include <iostream>

#include <list>

#include <map>

#include <numeric>

#include <queue>

#include <set>

#include <stack>

#include <vector>

#define ceil(a,b) (((a)+(b)-1)/(b))

#define endl '\n'

#define gcd __gcd

#define highBit(x) (1ULL<<(63-__builtin_clzll(x)))

#define popCount __builtin_popcountll

typedef long long ll;

using namespace std;

const int MOD = 1000000007;

const long double PI = acos(-1.L);

const int maxn = 10008;

const int inf = 0x7f7f7f7f;

int a[maxn];

int b[maxn];

int d[maxn];

int p[maxn];

int g[maxn];

int n;

void lis(int a[],int d[]){

	memset(g,inf,sizeof(g));

	int k;

	for (int i=1;i<=n;i++){

		k = lower_bound(g+1,g+n+1,a[i])-g;

		d[i] = k;

		g[k] = a[i];

	}

}

void print(int a[]){

	for (int i=1;i<=n;i++){

		printf("%d ",a[i]);

	}

	puts("");

}

void init(){

	for (int i=1;i<=n;i++){

		scanf("%d",&a[i]);

		b[n-i+1] = a[i];

	}

	memset(d,inf,sizeof(d));

	memset(p,inf,sizeof(p));

	lis(a,d);

	lis(b,p);

	int ans = 1;

	for (int i=1;i<=n;i++){

	//	if (d[i]==p[n-i+1]){

	//		cout << i << "----" << d[i] << endl;

	//		ans = max(ans,d[i] * 2 - 1);

	//	}

		ans = max(ans,min(d[i],p[n-i+1]) * 2 - 1);

	}

	printf("%d\n",ans);

	print(d);

	print(p);

}

int main() {

	//freopen("E:\\Code\\1.txt","r",stdin);

	while(scanf("%d",&n)!=EOF){

		init();

	}

	return 0;

}