题目描述

Farmer John 的奶牛们决定为 Farmer Nhoj 农场的奶牛们举办一场编程竞赛。为了使问题尽可能有趣，他们花费了大量时间来构造具有挑战性的测试用例。特别是对于一个问题，「Haybales」，奶牛们需要你的帮助来设计具有挑战性的测试用例。这有关解决以下这个有些奇妙的问题：

有一个有序整数数组 $x_1 \leq x_2 \leq \dotsb \leq x_N$（$1 \leq N \leq 10^5$），和一个整数 $K$。你不知道这个数组以及 $K$，但你知道对于每个索引 $i$ 使得 $x_{j_i} \leq x_i + K$ 的最大索引 $j_i$。保证有 $i\le j_i$ 以及 $j_1\le j_2\le \cdots \le j_N\le N$。

给定这些信息，Farmer John 的奶牛需要构造任意一个数组以及整数 $K$ 与该信息一致。构造需要满足对于所有 $i$ 有 $0 \leq x_i \leq 10^{18}$，并且 $1 \leq K \leq 10^{18}$。

可以证明这一定是可行的。请帮助 Farmer John 的奶牛们解决这一问题！

输入格式

输入的第一行包含 $N$。第二行包含 $j_1,j_2,\ldots,j_N$。

输出格式

输出 $K$，然后在下一行输出 $x_1,\ldots,x_N$。任何合法的输出均正确。

6
2 2 4 5 6 6

6
1
6
17
22
27
32

提示

【样例解释】

输出样例为数组 $a=[1,6,17,22,27,32]$ 以及 $K=6$。 $j_1=2$ 被满足是由于 $a_2=6 \le 1+6=a_1+K$ 而 $a_3=17>1+6=a_1+K$，从而 $a_2$ 是最大的不超过 $a_1+K$ 的元素。类似地：

• $j_2=2$ 被满足是由于 $a_2=6 \le 6+6$ 而 $a_3=17>6+6$；
• $j_3=4$ 被满足是由于 $a_4=22 \le 17+6$ 而 $a_5=27>17+6$；
• $j_4=5$ 被满足是由于 $a_5=27 \le 22+6$ 而 $a_5=32>22+6$；
• $j_5=6$ 被满足是由于 $a_6=32 \le 27+6$ 且 $a_6$ 是数组的最后一个元素；
• $j_6=6$ 被满足是由于 $a_6=32 \le 32+6$ 且 $a_6$ 是数组的最后一个元素。

对于输入样例，这并不是唯一正确的输出。例如，你也可以输出数组 $[1,2,4,5,6,7]$ 和 $K=1$。

【数据范围】

• 所有测试点的 $50\%$ 满足 $N \le 5000$。
• 其余测试点没有额外限制。

【说明】

本题采用自行编写的 Special Judge。如果对此有疑问或想要 hack，请私信编写者或发帖。