Card Game
Contest: Codeforces Round 899 (Div. 2)
Difficulty rating: 1500
Tags: brute force, greedy

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$$$.

Input format:
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}$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
4
4
-4 1 -3 5
4
1 -2 3 -4
3
-1 3 -5
1
-1

Example output:
5
4
2
0

Editorial:
Let's denote $$$i$$$-th card in the initial deck as card $$$i$$$.
Let the topmost card you'll pick in the initial deck as card $$$i$$$.
For all cards under card $$$i$$$ in initial deck, you can make only cards with the positive value to be choosed when they are in odd index.
Proof: Here is the strategy. Before you pick card $$$i$$$, if positive card(under card $$$i$$$ in initial deck) in odd index exists, choose it. Repeat this until all positive cards(under card $$$i$$$ in initial deck) are in even index. Then if you choose card $$$i$$$, all index of positive cards(under card $$$i$$$ in initial deck) will be decreased by $$$1$$$, and will become odd. Now, choose them from the bottom to top, so that the choosing won't effect the other positive cards' index.
Denote $$$prf_{j}$$$ as the sum of positive numbers among $$$a_{j}, a_{j+1}, \cdots, a_{n}$$$, and $$$prf_{n+1} = 0$$$. Since $$$prf_{j} = prf_{j+1} + \max \left( 0, a_{j}\right)$$$, $$$prf$$$ can be calculated in $$$\mathcal{O}(n)$$$.
You should necessarily pick card $$$i$$$ in index of $$$i$$$, and can pick all positive cards under card $$$i$$$ in initial deck, so your maximum final score will be $$$(i \% 2 == 1 ? a_{i} : 0) + prf_{i+1}$$$.
The answer is $$$\max \left( (i \% 2 == 1 ? a_{i} : 0) + prf_{i+1} \, | \, 1 \le i \le n \right)$$$.
There are lots of other solutions too.