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ź.