Problem C: 染色
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：1
Solved：1
Description
给定一个长度为 n 的正整数数组 A，其中所有数从左至右排成一排。
你需要将 A 中的每个数染成红色或蓝色之一，然后按如下方式计算最终得分：
你需要将 A 中的每个数染成红色或蓝色之一，然后按如下方式计算最终得分：
设 C 为长度为 n 的整数数组，对于 A 中的每个数 Ai（1≤i≤n）：
- 如果 Ai 左侧没有与其同色的数，则令 Ci=0。
- 否则，记其左侧与其最靠近的同色数为 Aj，若 Ai=Aj 则令 Ci =Ai ，否则令 Ci=0。
你的最终得分为 C 中所有整数的和，即i=1∑n Ci 。你需要最大化最终得分，请求出最终得分的最大值。
【数据范围】
对于所有测试数据，保证：，，。
Input
本题有多组测试数据。
输入的第一行包含一个正整数 T，表示数据组数。
接下来包含 T 组数据，每组数据的格式如下：
第一行包含一个正整数 n，表示数组长度。
第二行包含 n 个正整数 A1 ,A2 ,…,An ，表示数组 A 中的元素。
输入的第一行包含一个正整数 T，表示数据组数。
接下来包含 T 组数据，每组数据的格式如下：
第一行包含一个正整数 n，表示数组长度。
第二行包含 n 个正整数 A1 ,A2 ,…,An ，表示数组 A 中的元素。
Output
对于每组数据：输出一行包含一个非负整数，表示最终得分的最大可能值。
Sample Input Copy
3
3
1 2 1
4
1 2 3 4
8
3 5 2 5 1 2 1 4
Sample Output Copy
1
0
8
HINT
【样例 解释】
对于第一组数据，以下为三种可能的染色方案：
1. 将 A1,A2 染成红色，将 A3 染成蓝色（121），其得分计算方式如下：
- 对于 A1，由于其左侧没有红色的数，所以 C1=0。
- 对于 A2，其左侧与其最靠近的红色数为 A1。由于 A1=A2，所以 C2=0。
-
对于 A3，由于其左侧没有蓝色的数，所以 C3=0。
该方案最终得分为 C1+C2+C3=0。
2. 将 A1,A2,A3 全部染成红色（121），其得分计算方式如下：
- 对于 A1，由于其左侧没有红色的数，所以 C1=0。
- 对于 A2，其左侧与其最靠近的红色数为 A1。由于 A1=A2，所以 C2=0。
-
对于 A3，其左侧与其最靠近的红色数为 A2。由于 A2=A3，所以 C3=0。
该方案最终得分为 C1+C2+C3=0。
3. 将 A1,A3 染成红色，将 A2 染成蓝色（121），其得分计算方式如下：
- 对于 A1，由于其左侧没有红色的数，所以 C1=0。
- 对于 A2，由于其左侧没有蓝色的数，所以 C2=0。
-
对于 A3，其左侧与其最靠近的红色数为 A1。由于 A1=A3，所以 C3=A3=1。
该方案最终得分为 C1+C2+C3=1。
可以证明，没有染色方案使得最终得分大于 1。
对于第二组数据，可以证明，任何染色方案的最终得分都是 0。
对于第三组数据，一种最优的染色方案为将 A1,A2,A4,A5,A7 染为红色，将 A3,A6,A8 染为蓝色（35251214），其对应 C=[0,0,0,5,0,2,1,0]，最终得分为 8