← 返回题目列表

Codeforces · 1882/C

C. 卡牌游戏

中文机器翻译题面 查看原题

一副牌中有 $$$n$$$ 张牌。最初,$$$a_{i}$$$ 写在从顶部算起的第 $$$i$$$ 卡上。卡上写的值不会改变。

您将玩一个游戏。最初您的分数是 $$$0$$$。在每一回合中,您可以执行以下操作之一:

- 选择一个奇数$$$^{\dagger}$$$正整数$$$i$$$,该整数不大于牌堆中剩余的牌数。从牌堆顶部取出第 $$$i$$$ 卡,并将卡上写的数字添加到您的分数中。剩余的卡片将从顶部开始重新索引。
- 选择一个偶数$$$^{\ddagger}$$$正整数$$$i$$$,该整数不大于牌堆中剩余的牌数。从牌堆顶部取出第 $$$i$$$ 卡。剩余的卡片将从顶部开始重新索引。
- 结束游戏。您可以随时结束游戏,不必从初始牌组中移除所有牌。

游戏结束时你能得到的最高分数是多少?

$$$^{\dagger}$$$ 如果存在一个整数 $$$k$$$ 使得 $$$i = 2k + 1$$$,则整数 $$$i$$$ 是奇数。

$$$^{\ddagger}$$$ 如果存在一个整数 $$$k$$$ 使得 $$$i = 2k$$$,则整数 $$$i$$$ 是偶数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^{4}$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^{5}$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^{9} \le a_i \le 10^{9}$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^{5}$$$。

输出

对于每个测试用例,打印一个整数 - 游戏结束时可以获得的最高分数。

示例

输入 #1

4
4
-4 1 -3 5
4
1 -2 3 -4
3
-1 3 -5
1
-1

输出 #1

5
4
2
0

注意

在第一个测试用例中,可以得到$$$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$$$的分数结束游戏。