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

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