Поділ пасовища

Обмеження: 2 сек., 256 МіБ

Зеник з Марічкою нещодавно придбали для своїх жеребців велике пасовище.

Пасовище можна уявити, як довгу смугу з \(n\) ділянок. На \(i\)-ій ділянці (нумерація зліва направо) пасовища росте трава з поживністю \(a_i\). Значення \(a_i\) може бути від’ємним — це означає, що на \(i\)-ій ділянці росте трава, від якої більше шкоди, ніж користі.

Зеник і Марічка зрозуміли, що погарячкували з купівлею такого великого пасовища, і тепер чухають потилицю, що ж його робити.

Вони вирішили розділити пасовище парканом на дві частини й залишити собі одну частину, а іншу — продати. Паркан буде проходити між двома ділянками поля. Кожна з двох частин мусить містити хоча б одну ділянку. Перша (найлівіша) ділянка залишиться нашим конярам (конярі — це люди, що розводять коней, а ви що подумали?).

Зеник з Марічкою хочуть залишити собі частину з якомога більшою сумарною поживністю трави, а продати — з якомога меншою.

Нехай \(s_1\) — сума поживностей трави на ділянках, що залишаться Зеникові й Марічці, а \(s_2\) — сума на ділянках, які вони продадуть. Якої максимально можливої різниці \(s_1 - s_2\) можуть досягнути Зеник і Марічка?

Вхідні дані

У першому рядку задано ціле число \(n\) — кількість ділянок пасовища.

У другому рядку задано \(n\) цілих чисел \(a_i\) — поживність трави на \(i\)-ій ділянці пасовища.

Вихідні дані

У єдиному рядку виведіть ціле число — максимально можливе значення різниці \(s_1 - s_2\).

Обмеження

\(2 \le n \le 2 \cdot 10^5\),

\(|a_i| \le 10^9\).

Оцінювання складається з таких блоків:

• по 1 балу за кожен приклад з умови,

• 16 балів: усі числа мають однаковий знак,

• 47 балів: \(n \le 200\), \(|a_i| \le 10^6\),

• 33 бали: без додаткових обмежень.

Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 -5 3 7 2 -15 10 3	9

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 0 0 0 0	0

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 -50 -10 -10 30 -10	-30

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 1000000000 1000000000 1000000000 47 47	3000000000

Примітки

У першому прикладі з умови Зеник з Марічкою мають шість способів розділити пасовище на дві частини.

• Залишити собі \([-5]\) та продати \([3, 7, 2, -15, 10, 3]\). У цьому випадку \(s_1 = -5, s_2 = 3+7+2+(-15)+10+3=10, s_1-s_2=-5-10=-15\).

• Залишити собі \([-5, 3]\) та продати \([7, 2, -15, 10, 3]\). Тоді \(s_1 = -5 + 3 = -2, s_2 = 7+2+(-15)+10+3=7, s_1-s_2=-2-7=-9\).

• Залишити собі \([-5, 3, 7]\) та продати \([2, -15, 10, 3]\). Тоді \(s_1 = -5 + 3 + 7 = 5, s_2 = 2+(-15)+10+3=0, s_1-s_2=5-0=5\).

• Залишити собі \([-5, 3, 7, 2]\) та продати \([-15, 10, 3]\). Тоді \(s_1 = -5 + 3 + 7 + 2 = 7, s_2 = (-15)+10+3=-2, s_1-s_2=7-(-2)=9\).

• Залишити собі \([-5, 3, 7, 2, -15]\) та продати \([10, 3]\). Тоді \(s_1 = -5 + 3 + 7 + 2 + (-15) = -8, s_2 = 10+3=13, s_1-s_2=-8-13=-21\).

• Залишити собі \([-5, 3, 7, 2, -15, 10]\) та продати \([3]\). Тоді \(s_1 = -5 + 3 + 7 + 2 + (-15) + 10 = 2, s_2 = 3, s_1-s_2=2-3=-1\).

Максимально можлива різниця дорівнює \(9\).

У другому прикладі незалежно від поділу пасовища різниця дорівнює нулю.

У третьому прикладі відповідь від’ємна та дорівнює \(-30\).

У четвертому прикладі відповідь не поміщається в 32-бітове число.