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 x1≤x2≤⋯≤xNx1≤x2≤⋯≤xN (1≤N≤1051≤N≤105), and an integer KK. You don't know the array or KK, but you do know for each index ii, the largest index jiji such that xji≤xi**+Kxji≤xi+K. It is guaranteed that i≤jii≤ji and j1≤j2≤⋯≤jN≤**Nj1≤j2≤⋯≤jN≤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≤xi≤10180≤xi≤1018 for all ii and 1≤K≤10181≤K≤1018.

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

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains NN. The next line contains j1**,j2**,…,jNj1,j2,…,jN.

OUTPUT FORMAT (print output to the terminal / stdout):

Print KK, then x1**,…,xN**x1,…,xN on separate lines. Any valid output will be accepted.

SAMPLE INPUT:

6
2 2 4 5 6 6

SAMPLE OUTPUT:

6
1
6
17
22
27
32

The sample output is the array a=[1,6,17,22,27,32]a=[1,6,17,22,27,32] with K=6K=6. j1=2j1=2 is satisfied because a2=6≤1**+6=a1**+Ka2=6≤1+6=a1+K but a3**=17>1+6=a1**+Ka3=17>1+6=a1+K, so a2a2 is the largest element that is at most a1a1. Similarly,

• j2**=2j2=2 is satisfied because a2=6≤6+6a2=6≤6+6 but a3=17>6+**6a3=17>6+6
• j3**=4j3=4 is satisfied because a4=22≤17+6a4=22≤17+6 but a5=27>17+**6a5=27>17+6
• j4**=5j4=5 is satisfied because a5=27≤22+6a5=27≤22+6 but a5=32>22+**6a5=32>22+6
• j5**=6j5=6 is satisfied because a6=32≤27+**6a6=32≤27+6 and a6a6 is the last element of the array
• j6**=6j6=6 is satisfied because a6=32≤32+**6a6=32≤32+6 and a6a6 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.

SCORING:

• For 50% of all inputs, N≤5000N≤5000
• For the remaining inputs, there are no additional constraints.