CF1373D.Maximum Sum on Even Positions

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.

给你一个包含 $n$ 个整数的数组 $a$。数组下标从零开始（即第一个元素为 $a_0$，第二个元素为 $a_1$，依此类推）。

你可以至多反转该数组的一个子数组（连续子段）。注意：数组 $a$ 中边界为 $l$ 和 $r$ 的子数组定义为 $a[l; r] = a_l, a_{l + 1}, \dots, a_{r}$。

你的任务是选择一个子数组进行反转，使得反转后数组中所有偶数位置（即下标为 $0, 2, \dots, 2k$，其中 $k = \lfloor\frac{n-1}{2}\rfloor$）上的元素之和最大。

你需要回答 $t$ 个相互独立的测试用例。

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

输入的第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^4$），表示测试用例的数量。随后是 $t$ 个测试用例。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示数组 $a$ 的长度。每个测试用例的第二行包含 $n$ 个整数 $a_0, a_1, \dots, a_{n-1}$（$1 \le a_i \le 10^9$），其中 $a_i$ 是数组 $a$ 的第 $i$ 个元素。

保证所有测试用例中 $n$ 的总和不超过 $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$.

对于每个测试用例，在单独的一行上输出答案——即在最多反转一次数组 $a$ 的一个子数组（连续子段）后，所有偶数位置上的元素之和的最大可能值。