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

Input

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

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

Example

input

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

output

5
4
2
0

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

解题思路

　　一开始的做法是 dp，没想到贪心。不过这个 dp 的思考过程还挺麻烦的。

　　定义状态 $f(i,j)$ 表示从前 $i$ 个元素中删除了 $j$ 个的所有方案里分数的最大值。根据第 $i$ 元素是否删除来进行状态划分：

1. 如果不删除第 $i$ 个元素，那么有 $f(i,j) = f(i-1,j)$。
2. 如果删除第 $i$ 个元素，分三种情况：

• • $j = 0$：无法删除第 $i$ 个元素，有 $f(i,j) = f(i-1,j)$。
  • $j = 1$：由于至少要删除 $1$ 个元素，且要删除第 $i$ 个元素，因此只能删除第 $i$ 个元素，是否获得 $a_i$ 的分数只取决于 $i$ 的奇偶性，有 $f(i,j) = f(i-1,j-1) + (i \bmod 2) \cdot a_i$。
  • $j \geq 2$：如果 $a_i > 0$，为了获取分数，$i$ 是奇数的话可以先删除第 $i$ 个元素，再从前 $i-1$ 个元素中删除 $j-1$ 个元素；$i$ 是偶数的话可以先从前 $i-1$ 个元素中删除 $1$ 个元素，再删除原本的第 $i$ 个元素，然后再从原本的前 $i-1$ 个元素中删除 $j-2$ 个元素。如果 $a_i < 0$，同理，我们要将其变到偶数的下标再删除。有 $f(i,j) = f(i-1,j-1) + \max \{ 0, a_i \}$。

　　为此就有状态转移方程：$$\begin{cases} f(i,0) = f(i-1,0) ,& j = 0 \\ f(i,1) = \max \{ f(i-1,1), \, f(i-1,0) + (i \bmod 2) \cdot a_i \} ,& j=1 \\ f(i,j) = \max \{ f(i-1,j), \, f(i-1,j-1) + \max \{ 0, a_i \} \} ,& j \in [2,n] \end{cases}$$

　　那么最终答案就是 $\max\limits_{0 \leq i \leq n}{\{ f(n,i) \}}$。整个 dp 的时间复杂度为 $O(n^2)$，很明显会超时。可以发现其实我们只关注 $j$ 的三种情况：$j=0$，$j=1$，$j \geq 2$，而并不需要知道 $j$ 的确切值。为此我们直接把 $j$ 的所有可能取值压缩成 $3$ 种状态：$f(i,0)$ 表示从前 $i$ 个元素中删除 $0$ 个的所有方案里分数的最大值。$f(i,1)$ 表示从前 $i$ 个元素中删除恰好 $1$ 个的所有方案里分数的最大值。$f(i,2)$ 表示从前 $i$ 个元素中删除至少 $2$ 个的所有方案里分数的最大值。

　　状态转移方程直接对着上面改就可以了：$$\begin{cases} f(i,0) = f(i-1,0) \\ f(i,1) = \max \{ f(i-1,1), \, f(i-1,0) + (i \bmod 2) \cdot a_i \} \\ f(i,2) = \max \{ f(i-1,2), \, \max \{ f(i-1,1), f(i-1,2) \} + \max \{ 0, a_i \} \} \end{cases}$$

　　AC代码如下，时间复杂度为 $O(n)$：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 
 6 const int N = 2e5 + 10;
 7 
 8 int a[N];
 9 LL f[N][3];
10 
11 void solve() {
12     int n;
13     scanf("%d", &n);
14     for (int i = 1; i <= n; i++) {
15         scanf("%d", a + i);
16     }
17     f[0][0] = 0, f[0][1] = f[0][2] = -0x3f3f3f3f3f3f3f3f;
18     for (int i = 1; i <= n; i++) {
19         f[i][0] = f[i - 1][0];
20         f[i][1] = max(f[i - 1][1], f[i - 1][0] + i % 2 * a[i]);
21         f[i][2] = max(f[i - 1][2], max(f[i - 1][1], f[i - 1][2]) + max(0, a[i]));
22     }
23     printf("%lld\n", max({f[n][0], f[n][1], f[n][2]}));
24 }
25 
26 int main() {
27     int t;
28     scanf("%d", &t);
29     while (t--) {
30         solve();
31     }
32     
33     return 0;
34 }

　　然后再给出官方的贪心解法。

　　这里规定原序列中 $a_0$ 表示栈顶元素，$a_n$ 是栈底元素，即栈的开口在下标最小的处。

　　首先答案至少是 $0$，即一个元素都不删除的情况。否则至少要删除一个元素，对于所有的删除方案，这里按照中被删除元素的最小下标来进行分类，因此可以分成 $n$ 类。

　　假设被删除元素的最小下标是 $i$，那么在原序列中不可能再从 $[1,i-1]$ 中删除元素（获得分数），并且一定能够获得 $[i+1,n]$ 中所有的正整数分数。构造的方法如下，在删除的过程中只要在比 $i$ 大的下标里存在某个奇数下标是正整数，那么删除这个元素并获得分数，直到所有的奇数下标都不是正整数。此时偶数下标可能存在正整数，那么只要删除了第 $i$ 个元素，就会变成奇数下标，那么只需从最大的下标开始依次往前删除即可获得所有的正整数分数。而删除第 $i$ 个元素后从奇数下标变成的偶数下标不会再有正整数。

　　为此只需维护一个后缀和，然后枚举所有的 $i$ 作为被删除元素的最小下标，取所有情况的最大值即可。

　　AC 代码如下，时间复杂度为 $O(n)$：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 
 6 const int N = 2e5 + 10;
 7 
 8 int a[N];
 9 LL s[N];
10 
11 void solve() {
12     int n;
13     scanf("%d", &n);
14     for (int i = 1; i <= n; i++) {
15         scanf("%d", a + i);
16     }
17     s[n + 1] = 0;
18     for (int i = n; i; i--) {
19         s[i] = s[i + 1] + max(0, a[i]);
20     }
21     LL ret = 0;
22     for (int i = 1; i <= n; i++) {
23         ret = max(ret, s[i + 1] + i % 2 * a[i]);    // 由于必须删除a[i]，因此如果i是奇数则a[i]的分数必须获得
24     }
25     printf("%lld\n", ret);
26 }
27 
28 int main() {
29     int t;
30     scanf("%d", &t);
31     while (t--) {
32         solve();
33     }
34     
35     return 0;
36 }

参考资料

　　Codeforces Round 899 (Div. 2) Editorial：https://codeforces.com/blog/entry/120792

　　Codeforces Round 899 (Div. 2) A~D：https://zhuanlan.zhihu.com/p/658393910