Поділ пасовища
Limits: 2 sec., 256 MiB
Зеник з Марічкою нещодавно придбали для своїх жеребців велике пасовище.
Пасовище можна уявити, як довгу смугу з n ділянок. На i-ій ділянці (нумерація зліва направо) пасовища росте трава з поживністю ai. Значення ai може бути від’ємним — це означає, що на i-ій ділянці росте трава, від якої більше шкоди, ніж користі.
Зеник і Марічка зрозуміли, що погарячкували з купівлею такого великого пасовища, і тепер чухають потилицю, що ж його робити.
Вони вирішили розділити пасовище парканом на дві частини й залишити собі одну частину, а іншу — продати. Паркан буде проходити між двома ділянками поля. Кожна з двох частин мусить містити хоча б одну ділянку. Перша (найлівіша) ділянка залишиться нашим конярам (конярі — це люди, що розводять коней, а ви що подумали?).
Зеник з Марічкою хочуть залишити собі частину з якомога більшою сумарною поживністю трави, а продати — з якомога меншою.
Нехай s1 — сума поживностей трави на ділянках, що залишаться Зеникові й Марічці, а s2 — сума на ділянках, які вони продадуть. Якої максимально можливої різниці s1−s2 можуть досягнути Зеник і Марічка?
Input
У першому рядку задано ціле число n — кількість ділянок пасовища.
У другому рядку задано n цілих чисел ai — поживність трави на i-ій ділянці пасовища.
Output
У єдиному рядку виведіть ціле число — максимально можливе значення різниці s1−s2.
Constraints
2≤n≤2⋅105,
|ai|≤109.
Оцінювання складається з таких блоків:
по 1 балу за кожен приклад з умови,
16 балів: усі числа мають однаковий знак,
47 балів: n≤200, |ai|≤106,
33 бали: без додаткових обмежень.
Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 7 -5 3 7 2 -15 10 3 | 9 |
| Input (stdin) | Output (stdout) |
|---|---|
| 4 0 0 0 0 | 0 |
| Input (stdin) | Output (stdout) |
|---|---|
| 5 -50 -10 -10 30 -10 | -30 |
| Input (stdin) | Output (stdout) |
|---|---|
| 5 1000000000 1000000000 1000000000 47 47 | 3000000000 |
Notes
У першому прикладі з умови Зеник з Марічкою мають шість способів розділити пасовище на дві частини.
Залишити собі [−5] та продати [3,7,2,−15,10,3]. У цьому випадку s1=−5,s2=3+7+2+(−15)+10+3=10,s1−s2=−5−10=−15.
Залишити собі [−5,3] та продати [7,2,−15,10,3]. Тоді s1=−5+3=−2,s2=7+2+(−15)+10+3=7,s1−s2=−2−7=−9.
Залишити собі [−5,3,7] та продати [2,−15,10,3]. Тоді s1=−5+3+7=5,s2=2+(−15)+10+3=0,s1−s2=5−0=5.
Залишити собі [−5,3,7,2] та продати [−15,10,3]. Тоді s1=−5+3+7+2=7,s2=(−15)+10+3=−2,s1−s2=7−(−2)=9.
Залишити собі [−5,3,7,2,−15] та продати [10,3]. Тоді s1=−5+3+7+2+(−15)=−8,s2=10+3=13,s1−s2=−8−13=−21.
Залишити собі [−5,3,7,2,−15,10] та продати [3]. Тоді s1=−5+3+7+2+(−15)+10=2,s2=3,s1−s2=2−3=−1.
Максимально можлива різниця дорівнює 9.
У другому прикладі незалежно від поділу пасовища різниця дорівнює нулю.
У третьому прикладі відповідь від’ємна та дорівнює −30.
У четвертому прикладі відповідь не поміщається в 32-бітове число.