题目内容

有一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$，每个元素具有一个能量值。初始时，所有元素处于「空闲」状态。你可以选择任意一个元素，将其变为「激活」状态。之后，重复执行以下传播过程，直到序列中没有空闲元素：每个激活元素会将其所有相邻的空闲元素变为「共鸣」状态；每个共鸣元素会将其所有相邻的空闲元素变为「激活」状态（相邻定义为下标相差 $1$ 的元素，传播可视为同步进行，不会产生冲突）。最终，序列由激活元素和共鸣元素组成。你的得分为所有激活元素的能量值之和。请计算在所有可能的初始选择下，你能得到的最大得分。数据范围：测试数据组数 $T$ 不超过 100。对于每组数据，序列长度 $n$ 不超过 2*10^5，且所有测试数据的 $n$ 总和不超过 2*10^5。序列中的每个能量值均为正整数且不超过 10^9。

输入描述

第一行包含一个整数 $T$，表示测试数据的组数。接下来依次描述每组数据：第一行包含一个整数 $n$，表示序列的长度；第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示序列中的能量值。

输出描述

对于每组测试数据，输出一行一个整数，表示能够获得的最大得分。