codeforces#P1373D. Maximum Sum on Even Positions
Maximum Sum on Even Positions
Description
You are given an array consisting of integers. Indices of the array start from zero (i. e. the first element is , the second one is , and so on).
You can reverse at most one subarray (continuous subsegment) of this array. Recall that the subarray of with borders and is .
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 for integer should be maximum possible).
You have to answer independent test cases.
The first line of the input contains one integer () — the number of test cases. Then test cases follow.
The first line of the test case contains one integer () — the length of . The second line of the test case contains integers (), where is the -th element of .
It is guaranteed that the sum of does not exceed ().
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 .
Input
The first line of the input contains one integer () — the number of test cases. Then test cases follow.
The first line of the test case contains one integer () — the length of . The second line of the test case contains integers (), where is the -th element of .
It is guaranteed that the sum of does not exceed ().
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 .