Problem Description

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.

Input Format

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

Output Format

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

6
2 2 4 5 6 6

6
1
6
17
22
27
32

Hint

[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. If you have questions about this or want to hack, please private message the author or make a post.

Translated by ChatGPT 5