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.

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