Tests for Haybales

문제

Farmer John's cows have decided to offer a programming contest for the cows on Farmer Nhoj's farm. In order to make the problems as fun as possible, they have spent considerable time coming up with challenging input cases. For one problem in particular, "Haybales", the cows need your help devising challenging inputs. This involve solving the following somewhat intriguing problem:

There is an array of sorted integers $x_1\le x_2\le \cdots \le x_{N}x\_1\; \backslash leq\; x\_2\; \backslash leq\; \backslash dotsb\; \backslash leq\; x\_N$ ($1\le N\le {10}^{5}1\; \backslash leq\; N\; \backslash leq\; 10^5$), and an integer $KK$. You don't know the array or $KK$, but you do know for each index $ii$, the largest index $j_{i}j\_i$ such that $x_{j_i}\le x_i+Kx\_\{j\_i\}\; \backslash leq\; x\_i\; +\; K$. It is guaranteed that $i\le j_{i}i\backslash le\; j\_i$ and $j_1\le j_2\le \cdots \le j_N\le Nj\_1\backslash le\; j\_2\backslash le\; \backslash cdots\; \backslash le\; j\_N\backslash le\; N$.

Given this information, Farmer John's cows need to construct any array along with some integer $KK$ that matches that information. The construction needs to satisfy $0\le x_i\le {10}^{18}0\; \backslash leq\; x\_i\; \backslash leq\; 10^\{18\}$ for all $ii$ and $1\le K\le {10}^{18}1\; \backslash leq\; K\; \backslash leq\; 10^\{18\}$.

It can be proven that this is always possible. Help Farmer John's cows solve this problem!

입력

The first line of input contains $NN$. The next line contains $j_1,j_2,\dots ,j_{N}j\_1,j\_2,\backslash ldots,j\_N$.

출력

Print $KK$, then $x_1,\dots ,x_{N}x\_1,\backslash ldots,x\_N$ on separate lines. Any valid output will be accepted.

힌트

The sample output is the array $a=[1,6,17,22,27,32]a\; =\; [1,\; 6,\; 17,\; 22,\; 27,\; 32]$ with $K=6K\; =\; 6$. $j_1=2j\_1\; =\; 2$ is satisfied because $a_2=6\le 1+6=a_1+Ka\_2\; =\; 6\; \backslash leq\; 1\; +\; 6\; =\; a\_1\; +\; K$ but $a_3=17>1+6=a_1+Ka\_3\; =\; 17\; >\; 1\; +\; 6\; =\; a\_1\; +\; K$, so $a_{2}a\_2$ is the largest element that is at most $a_{1}a\_1$. Similarly,

• $j_2=2j\_2\; =\; 2$ is satisfied because $a_2=6\le 6+6a\_2\; =\; 6\; \backslash leq\; 6\; +\; 6$ but $a_3=17>6+6a\_3\; =\; 17\; >\; 6\; +\; 6$
• $j_3=4j\_3\; =\; 4$ is satisfied because $a_4=22\le 17+6a\_4\; =\; 22\; \backslash leq\; 17\; +\; 6$ but $a_5=27>17+6a\_5\; =\; 27\; >\; 17\; +\; 6$
• $j_4=5j\_4\; =\; 5$ is satisfied because $a_5=27\le 22+6a\_5\; =\; 27\; \backslash leq\; 22\; +\; 6$ but $a_5=32>22+6a\_5\; =\; 32\; >\; 22\; +\; 6$
• $j_5=6j\_5\; =\; 6$ is satisfied because $a_6=32\le 27+6a\_6\; =\; 32\; \backslash leq\; 27\; +\; 6$ and $a_{6}a\_6$ is the last element of the array
• $j_6=6j\_6\; =\; 6$ is satisfied because $a_6=32\le 32+6a\_6\; =\; 32\; \backslash leq\; 32\; +\; 6$ and $a_{6}a\_6$ is the last element of the array

This is not the only possible correct output for the sample input. For example, you could instead output the array $[1,2,4,5,6,7][1,\; 2,\; 4,\; 5,\; 6,\; 7]$ with $K=1K\; =\; 1$.

6
2 2 4 5 6 6

6
1
6
17
22
27
32