Гра на прямій

Limits: 2 sec., 256 MiB

Щоб не нудьгувати, Зеник із Марічкою вирішили зіграти в цікаву гру.

Гра відбувається на прямій, де розташовані \(n\) точок. Точки занумеровані від 1 до \(n\) зліва направо. Між кожною парою сусідніх точок записане одне ціле число (між точками з номерами \(і\) та \(і+1\) записано число \(a_i\)).

У гравця є одна фішка, яка спочатку стоїть у точці під номером 1. Він може пересунути свою фішку з будь-якої точки в будь-яку іншу. За це гравець заплатить штраф у розмірі модуля суми чисел, записаних між цими точками. Тобто якщо фішка була пересунута з позиції \(x\) на позицію \(y\), тоді гравець заплатить штраф у розмірі \(|\sum_{i=min\{x,y\}}^{max\{x,y\}-1} a_{і}|\) гривень.

Ціль гри — відвідати всі точки. Точка вважається відвіданою, якщо фішка була в ній хоча б один раз. Зауважте, що перша точка вважається відвіданою відразу ж на початку гри.

Зеник хоче похвалитися перед Марічкою своїми алгоритмічнимим здібностями. Для цього йому необхідно зіграти оптимально (заплативши найменшу можливу суму штрафу), але оскільки це завдання виявилось для нього занадто складним, допомогти йому маєте саме ви.

Input

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

У другому рядку задано \(n-1\) ціле число \(a_i\) — числа, записані між точками.

Output

У єдиному рядку виведіть ціле число — мінімальний штраф за гру.

Constraints

\(|a_i| \le 10^5\),

32% тестів: \(2 \le n \le 10\),

28% тестів: \(11 \le n \le 20\),

40% тестів: \(21 \le n \le 1000\).

Samples

Input (stdin) сopy	Output (stdout) сopy
6 5 -3 -3 4 -6	11

Notes

Один із можливих варіантів оптимальної гри:

\(1 \rightarrow 4 \rightarrow 6 \rightarrow 3 \rightarrow 5 \rightarrow 2\).

Штраф за пересування фішки між першою і четвертою точками — 1 гривня.

Штраф за пересування фішки між четвертою і шостою точками — 2 гривні.

Штраф за пересування фішки між шостою і третьою точками — 5 гривень.

Штраф за пересування фішки між третьою і п’ятою точками — 1 гривня.

Штраф за пересування фішки між п’ятою і другою точками — 2 гривні.

Отже, сумарний штраф — 11 гривень.