codeforces#P1373D. Maximum Sum on Even Positions

    ID: 31273 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>divide and conquerdpgreedyimplementation*1600

Maximum Sum on Even Positions

Description

You are given an array aa consisting of nn integers. Indices of the array start from zero (i. e. the first element is a0a_0, the second one is a1a_1, and so on).

You can reverse at most one subarray (continuous subsegment) of this array. Recall that the subarray of aa with borders ll and rr is a[l;r]=al,al+1,,ara[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 a0,a2,,a2ka_0, a_2, \dots, a_{2k} for integer k=n12k = \lfloor\frac{n-1}{2}\rfloor should be maximum possible).

You have to answer tt independent test cases.

The first line of the input contains one integer tt (1t21041 \le t \le 2 \cdot 10^4) — the number of test cases. Then tt test cases follow.

The first line of the test case contains one integer nn (1n21051 \le n \le 2 \cdot 10^5) — the length of aa. The second line of the test case contains nn integers a0,a1,,an1a_0, a_1, \dots, a_{n-1} (1ai1091 \le a_i \le 10^9), where aia_i is the ii-th element of aa.

It is guaranteed that the sum of nn does not exceed 21052 \cdot 10^5 (n2105\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 aa.

Input

The first line of the input contains one integer tt (1t21041 \le t \le 2 \cdot 10^4) — the number of test cases. Then tt test cases follow.

The first line of the test case contains one integer nn (1n21051 \le n \le 2 \cdot 10^5) — the length of aa. The second line of the test case contains nn integers a0,a1,,an1a_0, a_1, \dots, a_{n-1} (1ai1091 \le a_i \le 10^9), where aia_i is the ii-th element of aa.

It is guaranteed that the sum of nn does not exceed 21052 \cdot 10^5 (n2105\sum n \le 2 \cdot 10^5).

Output

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

Samples

输入数据 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