Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FZI_STEF - Stefan

Pan Stefan, powszechnie znany piosenkarz, planuje swoją największą trasę koncertową. Starannie wybrał miasta, w których chciałby zagrać oraz ustalił kolejnośc ich odwiedzania. Niestety badania rynku wykazały, że nie we wszystkich miastach zarobi (być może koszty organizacji koncertu będą większe niż zyski z biletów). Pan Stefan wydrukował już plakaty z listą planowanych koncertów, więc jedyne zmiany, na jakie mógłby sie zgodzić, to rozpoczęcie trasy być może później niż w pierwszym mieście na liście oraz zakończenie być może wcześniej niż w ostatnim mieście na liście.

Zadanie

Wyznacz, jaki jest największy możliwy zysk Pana Stefana na trasie otrzymanej w opisany powyżej sposób.

Wejście

Pierwsza linia wejścia zawiera jedną liczbę naturalną n (1≤n≤100 000) oznaczającą liczbę miast na trasie. W każdej z kolejnych n linii znajduje się jedna liczba całkowita z przedziału [-100 000,100 000] oznaczająca całkowity zysk lub stratę z organizacji koncertu w danym mieście.

Wyjście

Należy wypisać maksymalny możliwy zysk Pana Stefana.

Przykład

Wejście

5
1 
-2
4
5
-2

Wyjście

9

Wejście

2
-1
-2

Wyjście

0

Dodane przez:Rafal Nowak
Data dodania:2007-02-08
Limit czasu wykonania programu:0.200s-1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ADA95 ASM32 BASH BF CSHARP C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN GOSU HASK ICON ICK JAVA JS-RHINO LUA NEM NICE NODEJS OBJC OCAML PAS-GPC PERL PERL6 PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST SQLITE VB.NET WHITESPACE
Pochodzenie:Fajne Zawody Informatyczne
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.