P8098 [USACO22JAN] Tests for Haybales G

Farmer John’s cows decided to hold a programming contest for the cows on Farmer Nhoj’s farm. To make the problems as interesting as possible, they spent a lot of time constructing challenging test cases. In particular, for a problem called “Haybales”, the cows need your help to design challenging test cases. This is about solving the following somewhat strange problem: There is a sorted integer array $x_1 \leq x_2 \leq \dotsb \leq x_N$ ($1 \leq N \leq 10^5$), and an integer $K$. You do not know this array or $K$, but you do know, for each index $i$, the maximum index $j_i$ such that $x_{j_i} \leq x_i + K$. It is guaranteed that $i \le j_i$ and $j_1 \le j_2 \le \cdots \le j_N \le N$. Given this information, Farmer John’s cows need to construct any array and integer $K$ that are consistent with it. The construction must satisfy $0 \leq x_i \leq 10^{18}$ for all $i$, and $1 \leq K \leq 10^{18}$. It can be proven that this is always possible. Please help Farmer John’s cows solve this problem.

The first line contains $N$. The second line contains $j_1, j_2, \ldots, j_N$.

Output $K$, and then on the next line output $x_1, \ldots, x_N$. Any valid output is accepted.

[Sample Explanation] The sample output is the array $a = [1,6,17,22,27,32]$ and $K = 6$. The condition $j_1 = 2$ is satisfied because $a_2 = 6 \le 1 + 6 = a_1 + K$ and $a_3 = 17 > 1 + 6 = a_1 + K$, so $a_2$ is the largest element not exceeding $a_1 + K$. Similarly: - $j_2 = 2$ is satisfied because $a_2 = 6 \le 6 + 6$ and $a_3 = 17 > 6 + 6$; - $j_3 = 4$ is satisfied because $a_4 = 22 \le 17 + 6$ and $a_5 = 27 > 17 + 6$; - $j_4 = 5$ is satisfied because $a_5 = 27 \le 22 + 6$ and $a_5 = 32 > 22 + 6$; - $j_5 = 6$ is satisfied because $a_6 = 32 \le 27 + 6$ and $a_6$ is the last element of the array; - $j_6 = 6$ is satisfied because $a_6 = 32 \le 32 + 6$ and $a_6$ is the last element of the array. For the sample input, this is not the only correct output. For example, you could also output the array $[1,2,4,5,6,7]$ and $K = 1$. [Constraints] - For $50\%$ of the test cases, $N \le 5000$. - For the remaining test cases, there are no additional constraints. [Notes] This problem uses a self-written [Special Judge](https://www.luogu.com.cn/paste/kzgvkesl). If you have questions about this or want to hack, please [private message the author](https://www.luogu.com.cn/chat?uid=137367) or [make a post](https://www.luogu.com.cn/discuss/lists?forumname=P8098). Translated by ChatGPT 5