2219: 染色

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：1 Solved：0

Description

给定一个长度为 n 的正整数数组 A，其中所有数从左至右排成一排。
你需要将 A 中的每个数染成红色或蓝色之一，然后按如下方式计算最终得分：
设 C 为长度为 n 的整数数组，对于 A 中的每个数 Ai（1 ≤ i ≤ n）：
• 如果 Ai 左侧没有与其同色的数，则令 Ci = 0。
• 否则，记其左侧与. 其. 最. 靠. 近. 的. 同. 色. 数. 为 Aj，若 Ai = Aj，则令 Ci = Ai，否则令
Ci = 0。
你的最终得分为 C 中所有整数的和，即  。你需要最大化最终得分，请求出最
终得分的最大值

Input

从文件 color.in 中读入数据。
本. 题. 有. 多. 组. 测. 试. 数. 据。.
输入的第一行包含一个正整数 T，表示数据组数。
接下来包含 T 组数据，每组数据的格式如下：
第一行包含一个正整数 n，表示数组长度。
第二行包含 n 个正整数 A1, A2, . . . , An，表示数组 A 中的元素。

Output

输出到文件 color.out 中。
对于每组数据：输出一行包含一个非负整数，表示最终得分的最大可能值。

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 解释】
对于第一组数据，以下为三种可能的染色方案：
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
染为蓝色（35152124），其对应 C = [0, 0, 0, 5, 0, 1, 2, 0]，最终得分为 8。
【样例 2】
见选手目录下的 color/color2.in 与 color/color2.ans。
【数据范围】

对于所有测试数据，保证：1 ≤ T ≤ 10，2 ≤ n ≤ 2 × 105，1 ≤ Ai ≤ 106。

Source/Category