偶数位置的最大和

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个长度为 $n$ 的数组 $a$，下标从 $0$ 到 $n-1$。你可以选择至多一个连续区间并将其中元素的顺序翻转，也可以不进行操作。

求操作后所有偶数下标元素之和，即 $a_0+a_2+a_4+\cdots$ 的最大可能值。

输入格式

第一行包含一个整数 $t$，表示测试组数。

每组数据包含两行：第一行一个整数 $n$；第二行包含 $n$ 个整数 $a_0,a_1,\ldots,a_{n-1}$。

输出格式

对每组数据输出一行一个整数，表示所求最大值。

样例输入 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

数据范围

对于所有数据，$1\le t\le2\cdot10^4$，$1\le n\le2\cdot10^5$，$1\le a_i\le10^9$，且单个输入文件内所有测试组的 $n$ 之和不超过 $2\cdot10^5$。