P12809 [AMPPZ 2019] Cheese Game

Source: [AMPPZ 2019](https://amppz.tcs.uj.edu.pl/2019/data.html).

在参加了一年一度的**双人游戏与应用密码学研讨会**后，Alice 和 Bob 想通过玩他们最喜欢的游戏来放松。他们将 $n$ 片奶酪排成一排，编号从 $1$ 到 $n$。众所周知，尽管奶酪通常很美味，但某些切片可能比其他切片更美味——这就是为什么第 $i$ 片奶酪的美味度为 $o_i$。 Alice 先开始游戏，两位玩家轮流行动。在每次行动中，玩家可以吃掉仍然留在棋盘上的任意一组奶酪切片，条件是这组切片中不能包含任何两片相邻的切片（即编号为 $i$ 和 $i+1$ 的切片，其中 $1 \leq i \leq n - 1$）。我们假设切片的编号不会改变，因此在游戏过程中不会出现新的相邻对。 当然，两位玩家的目标都是最大化他们所吃奶酪切片的总美味度。 假设他们都采取最优策略，Alice 能够获得的最大分数是多少？

**本题单个测试点内有多组测试数据。** 输入的第一行包含测试数据数量 $z$（$1 \leq z \leq 20$）。每组测试数据的格式如下： - 测试数据的第一行包含奶酪切片数量 $n$（$1 \leq n \leq 100\,000$）。 - 第二行包含 $n$ 个整数 $o_1, o_2, \dots, o_n$（$1 \leq o_i \leq 1\,000\,000$）——每片奶酪的美味度。

对于每组测试数据，输出一个整数——假设双方都采取最优策略时，Alice 所吃奶酪切片的总美味度。