8711번 - Odchudzanie 다국어

문제

Kozik postanowił się odchudzić. Jest po n dniach diety i intensywnego treningu, jednak waga nie spadała mu równomiernie, a czasem nawet (ku zdziwieniu Kozika) zwiększała się.

Kozik codziennie zapisywał swoją wagę i teraz chce się pochwalić kolegom, więc wybierze taki fragment swojego dzienniczka, w którym schudł najbardziej. Znajdź ten fragment i policz, ile w nim schudł (czyli oblicz maksymalny spadek wagi Kozika).

입력

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita n (1 ≤ n ≤ 3 · 10⁶). W drugim wierszu wejścia znajduje się n liczb całkowitych w_k oznaczających wagę Kozika w k - tym dniu diety (1 ≤ w_k ≤ 10⁹).

출력

W pierwszym i jedynym wierszu wyjścia powinna być jedna liczba całkowita, oznaczająca maksymalny spadek wagi Kozika.

제한

힌트