POLSKI SPOJ

Wiele lat temu król Bajtazar chcąc urozmaicić drogę prowadzącą do zamku, rozkazał posadzić wzdłuż niej drzewa. Dzisiaj zdążyły one już osiągnąć pokaźne rozmiary, dzięki czemu wejście do zamku od niepamiętnych czasów nie wyglądało lepiej. Władca postanowił jednak jeszcze bardziej upiększyć otoczenie. Zdecydował zmienić wzrost drzew w taki sposób, aby były one ustawione rosnąco. Zadanie powierzył nadwornemu magowi Tadeuszowi.

Tadeusz zna potężne zaklęcie Abrakadabra, które pozwala użytkownikowi na manipulację rozmiarów dowolnego drzewa. Czar ten można rzucić z dowolną mocą, która definiuje maksymalną wartość o jaką można zmienić wysokość drzewa. Dla przykładu, zaklęcie o mocy s pozwala na zmniejszenie lub zwiększenie wysokości drzewa o maksymalnie s jednostek.

Taduesz chciałby znać najmniejszą moc zaklęcia, która pozwoli mu na wykonanie zadania powierzonego mu przez króla.

Wejście

W pierwszym wierszu wejścia znajduje się liczba całkowita n (1 ≤ n ≤ 10⁶) oznaczająca liczbę drzew posadzonych wzdłuż drogi.

W drugim wierszu znajduje się n liczb całkowitych h_i (1 ≤ h_i ≤ 10⁹), oznaczających wysokości kolejnych drzew.

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, równą minimalnej mocy zaklęcia umożliwiającej wykonanie zadania powierzonego Tadeuszowi.

Przykład

Dla danych wejściowych:
5
3 7 6 5 6
poprawnym wynikiem jest:

2