题目描述

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

有一个有序整数数组 $x_1 \leq x_2 \leq \dotsb \leq x_N$，和一个整数 $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 的奶牛们解决这一问题！

• $1 \leq N \leq 10^5$

输入格式

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

输出格式

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

6
2 2 4 5 6 6

6
2 2 4 5 6 6

测试点性质

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

题目提供者

供题：Danny Mittal