시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 22 8 6 33.333%

문제

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 · 106). W drugim wierszu wejścia znajduje się n liczb całkowitych wk oznaczających wagę Kozika w k - tym dniu diety (1 ≤ wk ≤ 109).

출력

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

예제 입력 1

5
6 7 5 4 2

예제 출력 1

5