Maija is the owner of the new and shiny shopping mall. The mall's gimmick is that it only has one entrance - but it's a really cool one! Internally, the mall is just one infinitely long corridor with shops on only one side. The mall entrance is on the opposite side of the shops and can have shops both to it's left and to it's right.

To combat this awful architecture, Maija needs to order the shops in such a way that the average distance to a shop's entrance is minimized. Of course, the shop owners will place their own entrances as close as possible to the mall entrance.

There are n shops numbered 1,2,\dots,n, the i-th of which requires a_i meters of space. Find a configuration where the average distance is minimized.

Input

The first line contains a single integer n.

The next line contains n integers a_1,\,a_2,\cdots,\,a_n.

Output

Print the minimum average distance. The solution is considered correct if its error is less than 10^{-3}.

Then, on a single line, print n real values - the positions of the shops' left sides relative to the mall's entrance. The shops may not overlap by more than 10^{-3}.

Constraints

• 1 \leq n \leq 10^5
• 1 \leq a_i \leq 10^4
• All input values are integers

Example 1

Input:

5
5 2 1 10 6

Output:

1.8
1 -2 0 6 -8

Example 2

Input:

2
9 1

Output:

0
0 -1