由于电信技术的发展，谣言的传播变得十分迅速。

现在有 $n$ 个人，依次编号为 $1, \dots, n$。

每个人都有一个最好的朋友，第 $i$ 个人的最好的朋友为 $a_i$（$a_i \neq i$）。

每个人都有一个真理捍卫者，第 $i$ 个人的真理捍卫者为 $b_i$（$b_i \neq i$）。由于奇妙的原因，一个人只会是恰好一个人的真理捍卫者，即 $b_1, \dots, b_n$ 是一个 $1$ 到 $n$ 的排列。

对于第 $i$ 个人我们定义他的影响系数，考虑下面这个假想的谣言传播：

1. 一开始，第 $i$ 个人从神奇的海螺那里听说了一则谣言。
2. 每次，如果第 $j$ 个人首次听说了这则谣言，那么：
   • 如果 $j$ 是 $i$ 的真理捍卫者，即 $j = b_i$， 那么 $j$ 会不做任何事。
   • 否则， $j$ 会打电话把这则谣言告诉他最要好的朋友 $a_j$。
3. 如果没有人首次听说了这则谣言那么传播过程结束。
4. 最终，听说了谣言的人数为第 $i$ 个人的影响系数。

一万万年后，一位考古学家得到了 $a_1, \dots, a_n$，然而 $b_1, \dots, b_n$ 的取值在漫漫的历史长河中消失了。现在这位考古学家想求出所有人的影响系数之和的最小值与最大值，并给出相应的一组解。

输入格式

第一行一个正整数 $n$。保证 $n \geq 2$。

第二行包含 $n$ 个整数 $a_1, \dots, a_n$。保证 $1 \leq a_i \leq n$ 且 $a_i \neq i$。

输出格式

第一行一个整数，表示影响系数之和的最小值。

接下来一行 $n$ 个整数 $b_1, \dots, b_n$ 表示一组满足影响系数之和最小的解。（如果有多组输出任意一组均可）

接下来一行一个整数，表示影响系数之和的最大值。

接下来一行 $n$ 个整数 $b_1, \dots, b_n$ 表示一组满足影响系数之和最大的解。（如果有多组输出任意一组均可）

样例一

input

5
4 1 5 3 4

output

11
4 1 5 3 2
18
2 5 4 1 3

样例二

见样例数据下载。

限制与约定

对于每个测试点，答对第一问可获得 50% 的分数，答对第二问可获得 50% 的分数。

请注意你输出的两组解必须合法否则该测试点会被直接判0分。（如果你输出的系数之和与解不相对应，只会导致该小问 $0$ 分，该测试点不会被直接判 $0$ 分）

时间限制：$1\texttt{s}$

空间限制：$256\texttt{MB}$

下载

样例数据下载