28753번 - Сэм и хранилище 다국어

문제

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

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

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

입력

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

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

출력

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

제한

힌트