Problem description


Giełda
(gielda)
Memory limit: 32 MB
Time limit: 1.00 s

Jasio odkrył właśnie swoje nadprzyrodzone zdolności – okazało się, że jest jasnowidzem i potrafi przewidzieć przyszłość. W związku z tym, odezwała się w nim chęć zarobku na swojej nowej umiejętności. Jasio nie będzie jednak wróżył z fusów czy kuli za pieniądze – tylko zagra na giełdzie.

Wybrał jedną firmę i skorzystał ze swoich możliwości przewidywania. Zapisał sobie na kartce zmiany wartości akcji tej firmy, które przewidział.

Teraz Jasio chce się dowiedzieć ile może maksymalnie zyskać na kupnie i sprzedaży jednej akcji we właściwych momentach (tylko jeden raz). Zysk to różnica między wartością akcji w momencie sprzedaży i wartością akcji w momencie kupna. Niestety Jasio nie odkrył jeszcze swoich zdolności informatycznych, za to odkrył, że Ty potrafisz programować i zaproponował Ci kilka procent zysków z przedsięwzięcia. Pomóż Jasiowi i sobie!

Napisz program, który: wczyta z wejścia przewidywania Jasia, obliczy maksymalny zysk, wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca liczbę zmian wartości akcji, które przewidział Jasio. W drugim (i ostatnim) wierszu wejścia znajduje się N liczb całkowitych Ai, pooddzielanych pojedynczymi odstępami. Są to wartości akcji w kolejnych chwilach.

Wyjście

Twój program powinien wypisać na wyjście dokładnie jedną liczbę całkowitą – maksymalny zysk z jednej akcji według przewidywań Jasia.

Ograniczenia

1 ≤ N ≤ 1 000 000, 0 ≤ Ai ≤ 109.

Częściowa punktacja

W testach wartych łącznie 35% maksymalnej punktacji: N ≤ 2 000.

Przykład

Input Output Explanation
5
4 3 5 6 2
3

Wystarczy kupić za 3, a sprzedać za 6.

Input Output Explanation
4
5 3 2 2
0

Jasiowi nie opłaca się nic robić, bo nic nie da się zyskać.