CF1882C Card Game

有 $n$ 张牌叠成一叠。最初，第 $i$ 张牌（从顶端开始计数）上写有 $a_i$。牌面上的数值不会改变。 你将进行一个游戏。最初你的得分为 $0$。每一回合，你可以进行以下操作之一： - 选择一个奇数 $i$（$i$ 是正整数，且不大于当前牌堆中剩余的牌数），移除从顶端开始的第 $i$ 张牌，并将该牌上的数值加到你的得分上。剩下的牌会重新从顶端编号。 - 选择一个偶数 $i$（$i$ 是正整数，且不大于当前牌堆中剩余的牌数），移除从顶端开始的第 $i$ 张牌。你的得分不变。剩下的牌会重新从顶端编号。 - 结束游戏。你可以在任意时刻结束游戏，不必移除所有的牌。 当游戏结束时，你最多能获得多少分？ $^\dagger$ 一个整数 $i$ 是奇数，当且仅当存在整数 $k$ 使得 $i = 2k + 1$。 $^\ddagger$ 一个整数 $i$ 是偶数，当且仅当存在整数 $k$ 使得 $i = 2k$。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每组测试用例的描述。 每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \le a_i \le 10^9$）。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示游戏结束时你能获得的最大得分。

在第一个测试用例中，可以按如下方式获得 $5$ 分： 1. 第一回合，选择 $i=2$。你的得分仍为 $0$，此时牌堆从顶端开始的数为 $[-4, -3, 5]$。 2. 第二回合，选择 $i=3$。你的得分变为 $5$，此时牌堆从顶端开始的数为 $[-4, -3]$。 3. 第三回合，结束游戏，得分为 $5$。 在第二个测试用例中，可以按如下方式获得 $4$ 分： 1. 第一回合，选择 $i=3$。你的得分变为 $3$，此时牌堆从顶端开始的数为 $[1, -2, -4]$。 2. 第二回合，选择 $i=1$。你的得分变为 $4$，此时牌堆从顶端开始的数为 $[-2, -4]$。 3. 第三回合，结束游戏，得分为 $4$。 在第三个测试用例中，可以按如下方式获得 $2$ 分： 1. 第一回合，选择 $i=1$。你的得分变为 $-1$，此时牌堆从顶端开始的数为 $[3, -5]$。 2. 第二回合，选择 $i=1$。你的得分变为 $2$，此时牌堆从顶端开始的数为 $[-5]$。 3. 第三回合，结束游戏，得分为 $2$。 由 ChatGPT 4.1 翻译