CF1882C.Card Game

There are $n$ cards stacked in a deck. Initially, $a_{i}$ is written on the $i$-th card from the top. The value written on a card does not change.

You will play a game. Initially your score is $0$. In each turn, you can do one of the following operations:

• Choose an odd$^{\dagger}$ positive integer $i$, which is not greater than the number of cards left in the deck. Remove the $i$-th card from the top of the deck and add the number written on the card to your score. The remaining cards will be reindexed starting from the top.
• Choose an even$^{\ddagger}$ positive integer $i$, which is not greater than the number of cards left in the deck. Remove the $i$-th card from the top of the deck. The remaining cards will be reindexed starting from the top.
• End the game. You can end the game whenever you want, you do not have to remove all cards from the initial deck.

What is the maximum score you can get when the game ends?

$^{\dagger}$ An integer $i$ is odd, if there exists an integer $k$ such that $i = 2k + 1$.

$^{\ddagger}$ An integer $i$ is even, if there exists an integer $k$ such that $i = 2k$.

牌堆中有 $n$ 张卡片。初始时，从上往下数第 $i$ 张卡片上写着数字 $a_{i}$。每张卡片上的数值不会改变。

你将进行一局游戏。初始时你的得分为 $0$。在每一回合中，你可以执行以下操作之一：

• 选择一个奇数$^{\dagger}$ 正整数 $i$，且 $i$ 不超过当前牌堆中剩余的卡片数量。移除牌堆顶部起第 $i$ 张卡片，并将该卡片上的数字加到你的得分中。剩余卡片将从顶部开始重新编号（即原第 $i+1$ 张变为新第 $i$ 张，依此类推）。
• 选择一个偶数$^{\ddagger}$ 正整数 $i$，且 $i$ 不超过当前牌堆中剩余的卡片数量。移除牌堆顶部起第 $i$ 张卡片。剩余卡片将从顶部开始重新编号。
• 结束游戏。你可以在任意时刻结束游戏，不必移除初始牌堆中的所有卡片。

当游戏结束时，你能获得的最大得分是多少？

$^{\dagger}$ 若存在整数 $k$ 使得 $i = 2k + 1$，则称整数 $i$ 为奇数。

$^{\ddagger}$ 若存在整数 $k$ 使得 $i = 2k$，则称整数 $i$ 为偶数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^{4}$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^{5}$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^{9} \le a_i \le 10^{9}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^{5}$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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}$。

For each test case, print a single integer — the maximum score you can get when the game ends.

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

In the first test case, one can get the score of $5$ as follows:

1. In the first turn, choose $i=2$. Your score remains $0$ and the numbers written on the cards from the top will become $[-4, -3, 5]$.
2. In the second turn, choose $i=3$. Your score will become $5$ and the numbers written on the cards from the top will become $[-4, -3]$.
3. In the third turn, end the game with the score of $5$.

In the second test case, one can get the score of $4$ as follows:

1. In the first turn, choose $i=3$. Your score will become $3$ and the numbers written on the cards from the top will become $[1, -2, -4]$.
2. In the second turn, choose $i=1$. Your score will become $4$ and the numbers written on the cards from the top will become $[-2, -4]$.
3. In the third turn, end the game with the score of $4$.

In the third test case, one can get the score of $2$ as follows:

1. In the first turn, choose $i=1$. Your score will become $-1$ and the numbers written on the cards from the top will become $[3, -5]$.
2. In the second turn, choose $i=1$. Your score will become $2$ and the numbers written on the cards from the top will become $[-5]$.
3. In the third turn, end the game with the score of $2$.

在第一个测试用例中，可以按如下方式获得分数 $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$ 结束游戏。