题目描述

我们称仅由 0 和 1 组成的字符串对 $(S,T)$ 满足以下所有条件时（且仅当满足时）为好字符串对：

• $S,T$ 中包含的 0 的个数相等。
• $S,T$ 中包含的 1 的个数相等。

特别地，对于好字符串对 $(S,T)$，$S,T$ 的长度相同。

对于好字符串对 $(S,T)$，定义无向图 $G(S,T)$ 如下：

• 设 $S$ 的长度为 $L$。构建一个包含顶点 $1,2,\cdots,L$ 的图 $g$。
• 设 $S$ 中 0 的个数为 $n$。记 $S$ 中 0 的下标为 $1\leq a_1<a_2<\cdots<a_n\leq L$，$T$ 中 0 的下标为 $1\leq b_1<b_2<\cdots<b_n\leq L$。对于每个 $1\leq i\leq n$，在 $g$ 中添加一条连接顶点 $a_i$ 和 $b_i$ 的边。
• 设 $S$ 中 1 的个数为 $m$。记 $S$ 中 1 的下标为 $1\leq c_1<c_2<\cdots<c_m\leq L$，$T$ 中 1 的下标为 $1\leq d_1<d_2<\cdots<d_m\leq L$。对于每个 $1\leq i\leq m$，在 $g$ 中添加一条连接顶点 $c_i$ 和 $d_i$ 的边。
• 经过上述步骤得到的 $g$ 即为 $G(S,T)$。

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\cdots,A_N)$。请找到一个满足以下所有条件的好字符串对 $(S,T)$：

• 设 $S$ 的长度为 $L$，满足 $N\leq L\leq 10^5$。
• 对于任意 $1\leq i,j\leq N$，当且仅当 $G(S,T)$ 中顶点 $i$ 和顶点 $j$ 属于同一连通分量时，有 $A_i=A_j$。

可以证明，在本题的限制下，解一定存在。

输入格式

输入通过标准输入给出，格式如下：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

请输出如下格式的答案：

$L$ $S$ $T$

其中，$L$ 是 $S,T$ 的长度。若有多个解，输出任意一个均可。

样例 1

输入

3
1 2 1

输出

4
0011
1100

样例 2

输入

5
1 2 3 4 5

输出

5
01010
01010

样例 3

输入

6
1 1 1 1 1 1

输出

6
011111
111110

样例 4

输入

10
1 2 3 2 4 3 4 4 5 6

输出

21
000101010111100011011
011010000010101111110

说明/提示

限制条件

• $1\leq N\leq 100$
• $1\leq A_i\leq N$
• 输入的所有值均为整数

样例解释 1

对于输出样例中的 $S,T$，构造 $G(S,T)$ 如下：

• 准备一个包含 $4$ 个顶点的图 $g$。
• $S$ 中 0 的下标为 $(1,2)$，$T$ 中 0 的下标为 $(3,4)$。在 $g$ 中添加边 $(1,3),(2,4)$。
• $S$ 中 1 的下标为 $(3,4)$，$T$ 中 1 的下标为 $(1,2)$。在 $g$ 中添加边 $(3,1),(4,2)$。
• $G(S,T)=g$。

$G(S,T)$ 的连通分量为顶点 $(1,3)$ 和顶点 $(2,4)$。这满足所有条件，因此该 $(S,T)$ 是正确的输出。

由 ChatGPT 4.1 翻译