D. Алгоритм трёх EXP
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Спустя годы Широ и Уайт оба поступили в THU. После того как на занятии они узнали об алгоритме EXP3 для задачи о многоруком бандите, им внезапно пришла в голову идея, и они придумали игру, не связанную с этим.

Есть $$$n$$$ позиций, расположенных в ряд и пронумерованных от $$$1$$$ до $$$n$$$ от начала к концу. Каждая позиция может находиться в одном из двух состояний: закрашена или не закрашена. Фишка Широ начинает на позиции $$$1$$$, а фишка Уайта — на позиции $$$2$$$. В начале игры закрашены только позиции $$$1$$$ и $$$2$$$.

Игроки ходят по очереди, и первым ходит Широ. На каждом ходу текущий игрок должен выбрать свою фишку и переместить её вперёд на количество шагов от $$$1$$$ до $$$4$$$ на незакрашенную позицию, после чего закрасить позицию, на которую он попал. Если игрок не может сделать допустимый ход (то есть все позиции на расстоянии от $$$1$$$ до $$$4$$$ шагов вперёд от его текущей позиции либо находятся за пределами $$$n$$$, либо уже закрашены), то он пропускает этот ход (то есть не делает ничего).

Игра заканчивается, когда ни Широ, ни Уайт не могут сделать ни одного допустимого хода. Легко доказать, что игра гарантированно завершится за конечное число шагов.

Для каждого $$$3\le k\le n$$$ позиция $$$k$$$ имеет положительный целочисленный вес $$$a_k$$$. Каждый раз, когда игрок закрашивает такую позицию $$$k$$$, его счёт увеличивается на $$$a_k$$$. И Широ, и Уайт начинают с нулевым счётом, и оба стремятся максимизировать разность между своим счётом и счётом соперника к концу игры.

Пусть $$$d=s_1-s_2$$$, где $$$s_1$$$ — счёт Широ, а $$$s_2$$$ — счёт Уайта. Широ и Уайт хотят узнать: если оба игрока действуют оптимально, чему будет равно $$$d$$$ после окончания игры? Поскольку эта задача слишком сложна, они обратились к вам из THUSAA. Вам нужно помочь им решить её.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$6\le n\le 10^5$$$) — количество позиций.

Вторая строка содержит $$$n-2$$$ целых числа $$$a_3, a_4, \ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$) — веса позиций с $$$3$$$ по $$$n$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — итоговое значение $$$d$$$.

Примеры
Входные данные
6
6
1 6 3 4
10
1 1 1 1 1 1 1 1
10
1 1 1 1 1 1 1 10
9
1 1 1 1 1 1 10
8
10 1 1 1 1 100
10
1000000000 1 1000000000 1 1000000000 1 1000000000 1
Выходные данные
5
0
-7
8
90
1000000000
Входные данные
6
9
7 6 2 2 5 8 7
10
8 26 18 1 11 9 15 9
11
8 3 9 2 3 4 8 8 7
12
5 6 5 3 1 2 1 1 5 4
15
6 6 7 2 2 2 5 2 2 4 7 7 7
18
7 4 5 1 2 6 7 5 7 3 7 3 6 5 6 6
Выходные данные
5
13
8
3
9
9
Примечание

Ниже приведено объяснение для первого примера:

Используем символ O для обозначения позиции, которую никто не посещал, S — для позиции, посещённой Широ, и W — для позиции, посещённой Уайтом. Тогда конечную конфигурацию можно представить строкой длины $$$n-2$$$, и эта строка однозначно соответствует последовательности ходов, сделанных обоими игроками.

Для первого набора входных данных рассмотрим первый ход Широ как игрока, начинающего игру:

  • Она не может перейти на позицию $$$2$$$, потому что она уже занята Уайтом;
  • Если её первый ход — на позицию $$$3$$$, то конечное состояние будет SWWS (разность счёта равна $$$-6$$$);
  • Если её первый ход — на позицию $$$4$$$, то конечное состояние будет OSSW (разность счёта равна $$$5$$$);
  • Если её первый ход — на позицию $$$5$$$, то конечное состояние будет OOSW (разность счёта равна $$$-1$$$);

Следовательно, оптимальное конечное состояние — OSSW, а разность счёта равна $$$5$$$.

Для второго набора входных данных возможное конечное состояние — SWSWSWSW, а разность счёта равна $$$0$$$.

Для третьего набора входных данных Уайт может за два хода занять самую дальнюю позицию $$$10$$$, до которой Широ не доберётся. Поэтому одна из возможных стратегий Широ — сделать большой ход вперёд, чтобы помешать Уайту откладывать ход дальше. Соответствующее конечное состояние — OOSWSSSW, а разность счёта равна $$$-7$$$.

Для четвёртого набора входных данных возможное конечное состояние — OOSWWWS, а разность счёта равна $$$8$$$.

Для пятого набора входных данных возможное конечное состояние — WWSWSS, а разность счёта равна $$$90$$$.

Для шестого набора входных данных возможное конечное состояние — OOSWSOWS, а разность счёта равна $$$1\,000\,000\,000$$$.