题目背景

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）决赛。

题解等资源可在 https://github.com/dapingguo8/THUPC2026-final 查看。

在单人操作的积木消除小游戏后，小 T 和小 S 还准备了一项双人互动的棋盘对弈小游戏。

游戏在一套特制的十周年纪念棋盘上进行。棋盘上面分布着带有分值的格子，参与的双方需要轮流控制棋子向前跳跃，抢占格子上的分数，以最大化自己和对手分数的差值。

题目描述

这套特制的棋盘由 $n$ 个格子组成，其中格子 $i \ (3 \le i \le n)$ 的分值为 正整数 $a_k$。

你决定与你的队友进行一场对弈。游戏开始时，你占据了格子 $1$ 并放上了自己的棋子，而你的队友占据了格子 $2$ 并放上了他的棋子，且此时仅有这两个格子被占据。双方的初始得分均为零。

游戏由你率先行动，之后双方轮流进行。在每个回合中，设当前行动玩家的棋子位于格子 $x$，则该玩家必须选择一个步数 $d \in \{1, 2, 3, 4\}$，满足 $x + d \le n$，且格子 $x + d$ 尚未被占据，然后将自己的得分加上该格子对应的分值 $a_{x + d}$，并将其棋子向前跳跃至格子 $x + d$。跳跃完成后，该玩家将占据这一新格子（请注意，该玩家之前占据的格子会一直被这一玩家占据）。特别地，若不存在任何合法的跳跃步数，该玩家本回合将无法行动并直接跳过。当双方均无法行动时，游戏结束，可以证明游戏一定会在有限步内结束。

显然，擅长博弈的你和你的队友都足够聪明，均会在对弈中采取最优策略。为了提前推演对局结果，你需要计算出在游戏结束时，你的总得分减去你的队友的总得分的值。

输入格式

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 $T \ (1 \le T \le 10 ^ 3)$，表示数据组数。对于每组测试数据：

• 第一行包含一个正整数 $n \ (6 \le n \le 10 ^ 5)$，表示棋盘的格子数量。
• 第二行包含 $n - 2$ 个正整数 $a_3, a_4, \dots, a_n \ (1 \le a_k \le 10 ^ 9)$，分别表示每个格子的分值。

保证所有测试数据中 $n$ 的和不超过 $10 ^ 5$。

输出格式

对于每组测试数据，输出一行一个整数，表示你的总得分减去你的队友的总得分的值。

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

提示

以下用一个长度为 $n$ 的字符串表示对局结果，其中字符 . 表示该格子未被任何人占据，字符 O 表示该格子被你占据，字符 X 表示该格子被你的队友占据。

对于第一组测试数据，在第一次行动中，你有以下三种选择：

• 选择步数 $d = 2$，将棋子跳跃至格子 $3$，则对局结果为 OXOXXO，得分差为 $-6$；
• 选择步数 $d = 3$，将棋子跳跃至格子 $4$，则对局结果为 OX.OOX，得分差为 $5$；
• 选择步数 $d = 4$，将棋子跳跃至格子 $5$，则对局结果为 OX..OX，得分差为 $-1$。

因此对局结果为 OX.OOX，得分差为 $5$。

对于第二组测试数据，一种可能的对局结果为 OXOXOXOX，得分差为 $0$。

对于第三组测试数据，一种可能的对局结果为 OX..OXOOOX，得分差为 $-7$。

对于第四组测试数据，一种可能的对局结果为 OX..OXXXO，得分差为 $8$。

对于第五组测试数据，一种可能的对局结果为 OXXXOXOO，得分差为 $90$。

对于第六组测试数据，一种可能的对局结果为 OX..OXO.XO，得分差为 $1000000000$。