Maximum Sum on Even Positions

题意翻译

### 题目描述 给定一个包含 $n$ 个元素的序列（下标从 $0$ 到 $n-1$），你可以选择一个连续区间进行翻转，使得翻转过后的序列偶数项的总和（即 $a_0,a_2,\ldots,a_{2k}$ 的和，其中 $k=\lfloor \dfrac{n-1}{2} \rfloor$）最大。 ### 输入格式 **本题有多组数据** 第一行一个整数 $t$ $(1 \leq t \leq 2 \times 10^4)$，表示数据的组数。 每组数据包含两行，第一行一个整数 $n$ $(1 \leq n \leq 2 \times 10^5)$，表示序列的长度。下一行 $n$ 个整数，表示序列 $a_i$。 保证 $\sum n \leq 2 \times 10^5$。 ### 输出格式 共 $t$ 行，每行一个数，表示该组数据的答案。

题目描述

You are given an array $ a $ consisting of $ n $ integers. Indices of the array start from zero (i. e. the first element is $ a_0 $ , the second one is $ a_1 $ , and so on). You can reverse at most one subarray (continuous subsegment) of this array. Recall that the subarray of $ a $ with borders $ l $ and $ r $ is $ a[l; r] = a_l, a_{l + 1}, \dots, a_{r} $ . Your task is to reverse such a subarray that the sum of elements on even positions of the resulting array is maximized (i. e. the sum of elements $ a_0, a_2, \dots, a_{2k} $ for integer $ k = \lfloor\frac{n-1}{2}\rfloor $ should be maximum possible). You have to answer $ t $ independent test cases.

输入输出格式

输入格式

The first line of the input contains one integer $ t $ ( $ 1 \le t \le 2 \cdot 10^4 $ ) — the number of test cases. Then $ t $ test cases follow. The first line of the test case contains one integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the length of $ a $ . The second line of the test case contains $ n $ integers $ a_0, a_1, \dots, a_{n-1} $ ( $ 1 \le a_i \le 10^9 $ ), where $ a_i $ is the $ i $ -th element of $ a $ . It is guaranteed that the sum of $ n $ does not exceed $ 2 \cdot 10^5 $ ( $ \sum n \le 2 \cdot 10^5 $ ).

输出格式

For each test case, print the answer on the separate line — the maximum possible sum of elements on even positions after reversing at most one subarray (continuous subsegment) of $ a $ .

输入输出样例

输入样例 #1

4
8
1 7 3 4 7 6 2 9
5
1 2 1 2 1
10
7 8 4 5 7 6 8 9 7 3
4
3 1 2 1

输出样例 #1

26
5
37
5