E. Веселая игра
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Однажды после очередного написанного соревнования по программированию Петя и Гена решили поиграть в какую-нибудь игру. Так как большинство современных игр кажутся им достаточно скучными, они любят придумывать свои собственные. В доступности нашлись только стикеры и ручки, но это их не остановило.

Они придумали следующую игру. Изначально они расклеили n стикеров в ряд на стене и написали на каждом стикере своё число. Далее они стали совершать ходы по очереди, причём Петя ходит первым.

В течение каждого хода происходит следующее. Пусть на стене сейчас висит m ≥ 2 стикеров. Игрок, которых ходит в данный момент, выбирает целое число k от 2 до m и забирает k стикеров с левого конца ряда себе. После этого он клеит новый стикер с левого конца ряда и пишет на нём число, равное сумме всех чисел на стикерах, которые он забрал себе на этом ходу.

Игра заканчивается, как только на стене остаётся один-единственный стикер. Счёт игрока определяется как сумма чисел, написанных на всех стикерах, которые он забрал себе. Каждый игрок стремится максимизировать разницу между своим количеством очков и количеством очков соперника.

Конечно же, Петя и Гена вкладывают другой смысл в понятие «играть в игру», нежели мы привыкли себе думать. Они уже разобрались, как по значению n и числам, написанным на каждом из стикеров исходно, определить разницу между Петиными и Гениными очками, если они будут играть оптимально. Справитесь ли вы с той же самой задачей?

Входные данные

В первой строке находится целое число n (2 ≤ n ≤ 200 000) — количество стикеров, которые исходно висят на стене.

Во второй строке находится n чисел a1, a2, ..., an ( - 10 000 ≤ ai ≤ 10 000) — числа, написанные на стикерах в порядке слева направо.

Выходные данные

Выведите одно число — разность между количеством очков у Пети и Гены в конце игры, если они играют оптимально.

Примеры
Входные данные
3
2 4 8
Выходные данные
14
Входные данные
4
1 -7 -2 3
Выходные данные
-3
Примечание

В первом тесте из условия оптимальным ходом для Пети будет сразу взять себе все имеющиеся стикеры, в результате чего счёт Пети составит 14, а счёт Гены — 0.

Во втором тесте из условия оптимальная последовательность ходов для игроков выглядит следующим образом. На первом ходу Петя возьмёт себе первые три стикера и добавит слева от ряда стикер с числом  - 8. На втором ходу Гена возьмёт себе оставшиеся два стикера. Счёт Пети составит 1 + ( - 7) + ( - 2) =  - 8, а счёт Гены — ( - 8) + 3 =  - 5, значит разность очков Пети и Гены составит  - 3.