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