Piorunochron
Limit pamięci: 128 MB
Postępujące zmiany klimatu zmusiły władze Bajtogrodu do wybudowania dużego piorunochronu,
który chroniłby wszystkie budynki w mieście.
Wszystkie budynki stoją w rzędzie przy jednej prostej ulicy i są ponumerowane
kolejno od do
.
Zarówno wysokości budynków, jak i wysokość piorunochronu wyrażają się nieujemnymi liczbami całkowitymi. Bajtogród dysponuje funduszami na wybudowanie tylko jednego piorunochronu. Co więcej, im wyższy ma być piorunochron, tym będzie droższy.
Aby piorunochron o wysokości umieszczony na dachu budynku
(o wysokości
) mógł skutecznie chronić wszystkie budynki,
dla każdego innego budynku
(o wysokości
) musi zachodzić następująca nierówność:
Tutaj oznacza wartość bezwzględną różnicy liczb
oraz
.
Bajtazar, burmistrz Bajtogrodu, poprosił Cię o pomoc.
Napisz program, który dla każdego budynku obliczy, jaka jest minimalna wysokość piorunochronu,
który umieszczony na budynku
będzie chronił wszystkie budynki.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita
(
) oznaczająca liczbę budynków w Bajtogrodzie.
W każdym z kolejnych
wierszy znajduje się jedna liczba całkowita
(
),
oznaczająca wysokość
-tego budynku.
Wyjście
Twój program powinien wypisać na standardowe wyjście wierszy.
W
-tym wierszu powinna znaleźć się nieujemna liczba całkowita
, oznaczająca minimalną wysokość
piorunochronu na
-tym budynku.
Przykład
Dla danych wejściowych:
6 5 3 2 4 2 4
poprawną odpowiedzią jest:
2 3 5 3 5 4
Autor zadania: Piotr Niedźwiedź.