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

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

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

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

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

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

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