Сэм и хранилище
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сэм и Ловец одновременно нашли хранилище портативных хиральных конструкторов. Всего в хранилище $$$n$$$ конструкторов, они лежат в ряд и на каждом написана его мощность $$$a_i$$$. Сэм и Ловец будут ходить по-очереди.

На своем ходу каждый игрок может сломать несколько, возможно $$$0$$$, первых конструкторов в ряду и взять следующий, после чего ход заканчивается. Конструкторы рассматриваются в порядке увеличения номеров, то есть очередной конструктор может быть сломан или взят только тогда, когда сломаны или взяты все конструкторы с меньшими номерами. Процесс продолжается до тех пор, пока в ряду остался хотя бы один конструктор. Каждый игрок стремится максимизировать разность между суммой мощностей конструкторов, которые взял он, и конструкторов, взятых противником.

Сэм ходит первым, помогите ему определить разность суммы мощностей конструкторов, который возьмет он, и конструкторов, которые возьмет Ловец, при условии, что оба игрока играют оптимально.

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

В первой строке дано одно целое число $$$n$$$ — количество конструкторов ($$$1 \le n \le 200\,000$$$).

Во второй строке дано $$$n$$$ целых чисел $$$a_i$$$, $$$i$$$-е число обозначает мощность $$$i$$$-го конструктора ($$$1 \le a_i \le 10^9$$$).

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

В единственной строке выведите одно целое число — ответ на задачу.

Примеры

Входные данные
3
1 2 3
Выходные данные
3
Входные данные
3
3 2 1
Выходные данные
2