题目描述
给定一个长度为 $ n $ 的正整数数组 $ A $ ，其中所有数从左至右排成一排。
你需要将 $ A $ 中的每个数染成红色或蓝色之一，然后按如下方式计算最终得分：
设 $ C $ 为长度为 $ n $ 的整数数组，对于 $ A $ 中的每个数 $ A_i（1≤i≤n） $ ：
- 如果 $ A_i $ 左侧没有与其同色的数，则令 $ C_i=0 $ 。
- 否则，记其左侧与.其.最.靠.近.的.同.色.数.为 $ A_j $ ，若 $ A_i=A_j $ ，则令 $ C_i=A_i $ ，否则令 $ C_i=0 $ 。
你的最终得分为 $ C $ 中所有整数的和，即$\displaystyle\sum_{i=1}^{n}C_i$。你需要最大化最终得分，请求出最终得分的最大值。
输入格式
从文件 $ color.in $ 中读入数据。
本题有多组测试数据。
输入的第一行包含一个正整数 $ T $ ，表示数据组数。
接下来包含 $ T $ 组数据，每组数据的格式如下：
第一行包含一个正整数 $ n $ ，表示数组长度。
第二行包含 $ n $ 个正整数 $ A_1,A_2,...,A_n $ ，表示数组 $ A $ 中的元素。
输出格式
样例输入1
3
3
1 2 1
4
1 2 3 4
8
3 5 2 5 1 2 1 4
样例输出1
1
0
8
样例1解释
对于第一组数据，以下为三种可能的染色方案：
1.将 $ A_1,A_2 $ 染成红色，将 $ A_3 $ 染成蓝色 $ （121） $ ，其得分计算方式如下：
•对于 $ A_1 $ ，由于其左侧没有红色的数，所以 $ C_1=0 $ 。
•对于 $ A_2 $ ，其左侧与其最靠近的红色数为 $ A_1 $ 。由于 $ A_1\ \ne\ A_2 $ ，所以 $ C_2=0 $ 。
•对于 $ A_3 $ ，由于其左侧没有蓝色的数，所以 $ C_3=0 $ 。
该方案最终得分为 $ C_1+C_2+C_3=0 $ 。
2.将 $ A_1,A_2,A_3 $ 全部染成红色 $ （121） $ ，其得分计算方式如下：
•对于 $ A_1 $ ，由于其左侧没有红色的数，所以 $ C_1=0 $ 。
•对于 $ A_2 $ ，其左侧与其最靠近的红色数为 $ A_1 $ 。由于 $ A_1\ \ne\ A_2 $ ，所以 $ C_2=0 $ 。
•对于 $ A_3 $ ，其左侧与其最靠近的红色数为 $ A_2 $ 。由于 $ A_2\ \ne\ A_3 $ ，所以 $ C_3=0 $ 。
该方案最终得分为 $ C_1+C_2+C_3=0 $ 。
3.将 $ A_1,A_3 $ 染成红色，将 $ A_2 $ 染成蓝色 $ （121） $ ，其得分计算方式如下：
•对于 $ A_1 $ ，由于其左侧没有红色的数，所以 $ C_1=0 $ 。
•对于 $ A_2 $ ，由于其左侧没有蓝色的数，所以 $ C_2=0 $ 。
•对于 $ A_3 $ ，其左侧与其最靠近的红色数为 $ A_1 $ 。由于 $ A_1=A_3 $ ，所以 $ C_3=A_3=1 $ 。
该方案最终得分为 $ C_1+C_2+C_3=1 $ 。
可以证明，没有染色方案使得最终得分大于 $ 1 $ 。
对于第二组数据，可以证明，任何染色方案的最终得分都是 $ 0 $ 。
对于第三组数据，一种最优的染色方案为将 $ A_1,A_2,A_4,A_5,A_7 $ 染为红色，将 $ A_3,A_6,A_8 $ 染为蓝色 $ （35152124） $ ，其对应 $ C=[0,0,0,5,0,1,2,0] $ ，最终得分为 $ 8 $ 。
样例2
见选手目录下的 $ color/color2.in $ 与 $ color/color2.ans $ 。
提示
数据范围
