Arxeoloqlar

Xəzinə ovçuları komandanız yeni bir arxeoloji abidə kəşf edib. Bu abidə qiymətli metallar və qədim əşyalarla doludur və bir xətt boyunca yerləşən $n$ qazıntı yerindən ibarətdir.

İlkin planlara əsasən, hər bir qazıntı yerinin xalis mənfəət gətirəcəyi gözlənilir. $i$-ci yerin mənfəəti $p_i$ ilə ifadə olunur. Bu o deməkdir ki, komandanız $i$-ci yerdə qazılan hər metr üçün $p_i$ dollar qazanacaq. Qeyd etmək lazımdır ki, $p_i$ mənfi də ola bilər, bu isə həmin yerdə qazıntı texnikasının istismar xərclərinin qazıntıdan əldə edilən faktiki faydanı üstələdiyini göstərir.

Ən gəlirli yerlərdə mümkün qədər çox qazmaq istəyəcəksiniz. Lakin, sürüşmələrin qarşısını almaq üçün çox dik yamaclar olmamalıdır. Dəqiq desək, hər hansı iki qonşu nöqtə üçün bu nöqtələrdə qazma dərinliyi arasındakı fərq 1 metrdən çox ola bilməz. Xüsusilə, 1 və $n$ yerləri yalnız 1 metr dərinliyə qədər qazıla bilər.

Bu şərtlər altında maksimum xalis mənfəəti nə qədər əldə edə bilərsiniz?

Məsələn, aşağıda birinci nümunə üçün optimal olan qazıntı planı təsvir edilmişdir. Belə bir planın xalis mənfəəti $8$-ə bərabərdir.

Giriş verilənləri

Birinci sətir təbii ədəd $n(1\le n\le 250000)$-i ehtiva edir.

İkinci sətir $n$ tam ədəd $p_i(-10^6\le p_i\le 10^6)$-i ehtiva edir.

Çıxış verilənləri

Bir tam ədəd çıxarın - əldə edə biləcəyiniz ən böyük mənfəət.

Nümunələr