CF2215D EXPloration, EXPloitation, and Gain Some EXPerience!

多年以后，Shiro 和 White 都考入了 THU。在课堂上学习了“多臂赌博机”问题的 EXP3 算法后，他们突发奇想，设计了一个与此无关的游戏。 有 $n$ 个位置排成一行，从前到后编号为 $1,2,\ldots,n$。每个位置有黑化和未黑化两种状态。Shiro 的棋子起始位于位置 $1$，White 的棋子起始位于位置 $2$，并且开始时只有 $1$ 和 $2$ 这两个位置为黑化状态。 两位玩家轮流行动，Shiro 先手。每轮轮到当前玩家时，必须选择自己的棋子，并向前跳 $1$ 到 $4$ 步，跳到一个未被黑化的位置，同时将该位置黑化。如果某位玩家无法进行合法的移动（即他当前位置前方 $1$ 到 $4$ 步内所有位置都超出了 $n$ 或已经被黑化），则该玩家本轮跳过，不做任何操作。 当 Shiro 和 White 都无法再进行合法移动时，游戏结束。容易证明，游戏一定在有限步内结束。 对于每个 $3\le k\le n$，位置 $k$ 有一个正整数权值 $a_k$。每当有玩家黑化位置 $k$，其得分就增加 $a_k$。Shiro 和 White 初始分数均为 $0$，他们都想最大化自己与对方分数的差，即游戏结束时 $d=s_1-s_2$，其中 $s_1$ 为 Shiro 的得分，$s_2$ 为 White 的得分。 给定所有权值，当两位玩家都采用最优策略时，最终 $d$ 的值是多少？Shiro 和 White 求解无果，只好向你求助。请你帮他们解决这个问题。

每个测试点包含多组测试数据。第一行为测试组个数 $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$ 的值。

以下为第一个样例的解释： 用字符 O 表示未被任何人访问的位置，S 表示被 Shiro 访问的位置，W 表示被 White 访问的位置。那么最终配置可用长度为 $n-2$ 的字符串表示，这个字符串与两人移动的顺序一一对应。 对于第一个测试样例，假设 Shiro 首先行动： - 她不能去 $2$，因为已经被 White 占据； - 如果她第一步去 $3$，最终状态为 SWWS（分数差 $-6$）； - 如果第一步去 $4$，最终状态为 OSSW（分数差 $5$）； - 如果第一步去 $5$，最终状态为 OOSW（分数差 $-1$）； 因此，最优最终状态是 OSSW，分数差为 $5$。 对于第二个样例，一种可能的最终状态是 SWSWSWSW，分数差为 $0$。 对于第三个样例，White 可以在两步内占据最远处 $10$，Shiro 无法到达。因此 Shiro 最优策略是大步跃进防止 White 拖延，最终状态 OOSWSSSW，分数差为 $-7$。 对于第四个样例，一种可能的最终状态是 OOSWWWS，分数差为 $8$。 对于第五个样例，一种可能的最终状态是 WWSWSS，分数差为 $90$。 对于第六个样例，一种可能的最终状态是 OOSWSOWS，分数差为 $1\,000\,000\,000$。 由 ChatGPT 5 翻译