In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.

If you are familiar with IRC chat, the support team is also reachable on PIRC network (`irc.pirc.pl`

) in `#szkopul`

channel. If you are not, just use email.

Please do not ask us things like "how to solve task XYZ?".

Please remember that the support team has to sleep sometimes or go to work in real life.

Byteasar loved to play with building blocks as a child. He used to arrange the blocks into columns of random height and then organize them in the following manner: Byteasar would choose a number and try to arrange the blocks in such a way that some consecutive columns would be of equal height. Furthermore he always tried to achieve this goal in a minimum number of moves possible, where a single move consists in:

- laying one block on top of any column (Byteasar had a huge box with spare blocks, ensuring this move could always be performed), or
- removing the uppermost block from the top of any column.

However, Byteasar was never quite sure if his sequence of moves was indeed optimal, therefore he has asked you to write a programme that will help him solve the problem.

Write a programme that:

- reads the number along with the initial setup of the blocks from the standard input,
- determines the optimal solution (shortest possible sequence of moves),
- writes out the solution to the standard output.

In the first line of the standard input there are two integers, and (), separated by a single space. Each of the following lines contains the height of some column; the line no. contains the integer - the height of the column, ie. the number of blocks it consists of.

The optimal solution should be written out to the standard output, ie. such arrangement of blocks that:

- contains consecutive columns of equal height,
- can be obtained from the initial setup in a minimum possible number of moves.

For the input data:

5 3 3 9 2 3 1

the correct result is:

2 3 9 2 2 2

*Task author: Tomasz Walen.*