一副牌中有 $$$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$$$的分数结束游戏。