Aproksymacja kontratakuje

Limit pamięci: 64MB

Niech dany będzie ciąg liczb całkowitych a1, ..., an. Poszukujemy niemalejącego ciągu rzeczywistego b1, ..., bn, dla którego liczba

wa,b=|a1-b1| + ... + |an-bn|

jest jak najmniejsza.

Zadanie

Napisz program, który:

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita n (1 <= n <= 1.000.000). Kolejnych n wierszy wejścia zawiera n liczb całkowitych ai (-106 <= ai <= 106).

Wyjście

Pierwszy wiersz wyjścia powinien zawierać jedną liczbę rzeczywistą - minimalną możliwą do uzyskania wartość wyrażenia wa,b. Kolejnych n wierszy powinno zawierać po jednej liczbie rzeczywistej bi. Każda liczba na wyjściu powinna być wypisana z co najmniej trzema i co najwyżej dziesięcioma cyframi po kropce dziesiętnej (i musi być wypisana w formacie typu 0.05 a nie 5e-2 czy .05, czyli w standardowym zapisie liczb rzeczywistych).

Przykład

Dla danych wejściowych:

4
3
1
4
2

poprawnym wynikiem jest na przykład:

4.00000000
2.0000000
2.000000
3.000000000
3.0000