时间限制：1000 ms
内存限制：128 MiB
标准输入输出
题目类型：传统
评测方式：文本比较
给定一个长度为 的正整数数组 ，其中所有数从左至右排成一排。
你需要将 中的每个数染成红色或蓝色之一，然后按如下方式计算最终得分：
设 为长度为 的整数数组，对于 中的每个数 （）：
- 如果 左侧没有与其同色的数，则令 。
- 否则，记其左侧与其最靠近的同色数为 ，若 ，则令 ，否则令 。
你的最终得分为 中所有整数的和，即 。你需要最大化最终得分，请求出最终得分的最大值。
本题有多组测试数据。
输入的第一行包含一个正整数 ，表示数据组数。
接下来包含 组数据，每组数据的格式如下：
第一行包含一个正整数 ，表示数组长度。
第二行包含 个正整数 ，表示数组 中的元素。
对于每组数据：输出一行包含一个非负整数，表示最终得分的最大可能值。
样例输入 1
复制3
3
1 2 1
4
1 2 3 4
8
3 5 2 5 1 2 1 4
样例输出 1
样例解释 1
对于第一组数据，以下为三种可能的染色方案：
- 将 染成红色，将 染成蓝色（），其得分计算方式如下：
- 对于 ，由于其左侧没有红色的数，所以 。
- 对于 ，其左侧与其最靠近的红色数为 。由于 ，所以 。
- 对于 ，由于其左侧没有蓝色的数，所以 。
该方案最终得分为 。
- 将 全部染成红色（），其得分计算方式如下：
- 对于 ，由于其左侧没有红色的数，所以 。
- 对于 ，其左侧与其最靠近的红色数为 。由于 ，所以 。
- 对于 ，其左侧与其最靠近的红色数为 。由于 ，所以 。
该方案最终得分为 。
- 将 染成红色，将 染成蓝色（），其得分计算方式如下：
- 对于 ，由于其左侧没有红色的数，所以 。
- 对于 ，由于其左侧没有蓝色的数，所以 。
- 对于 ，其左侧与其最靠近的红色数为 。由于 ，所以 。
该方案最终得分为 。
可以证明，没有染色方案使得最终得分大于 。
对于第二组数据，可以证明，任何染色方案的最终得分都是 。
对于第三组数据，一种最优的染色方案为将 染为红色，将 染为蓝色（），其对应 ，最终得分为 。
样例 2
见选手目录下的 color/color2.in 与 color/color2.ans。