染色

• 时间限制：1 秒
• 内存限制：512 MiB

题目描述

给定一个长度为 $n$ 的正整数数组 $A$。你需要把每个数染成红色或蓝色。

定义长度同为 $n$ 的数组 $C$。对于每个位置 $i$：

• 如果 $A_i$ 左侧没有与它同色的数，则 $C_i=0$；
• 否则，设 $A_j$ 是它左侧距离最近的同色数。若 $A_i=A_j$，则 $C_i=A_i$；否则 $C_i=0$。

一种染色方案的得分为 $\sum_{i=1}^{n}C_i$。请计算所有染色方案中的最大得分。

输入格式

本题有多组测试数据。

第一行一个正整数 $T$，表示测试数据组数。

对于每组数据：

• 第一行一个正整数 $n$；
• 第二行 $n$ 个正整数 $A_1,A_2,\ldots,A_n$。

输出格式

对于每组数据，输出一行一个非负整数，表示最大可能得分。

样例输入

3
3
1 2 1
4
1 2 3 4
8
3 5 2 5 1 2 1 4

样例输出

1
0
8

样例说明

第一组数据中，可以把第 $1,3$ 个数染成红色，把第 $2$ 个数染成蓝色。此时只有第 $3$ 个数产生贡献 $1$。

第二组数据中所有数互不相同，任何染色方案的得分均为 $0$。

第三组数据的一种最优方案是把第 $1,2,4,5,7$ 个数染成红色，把第 $3,6,8$ 个数染成蓝色，对应 $C=[0,0,0,5,0,2,1,0]$，得分为 $8$。

数据范围

对于所有测试数据，保证：

• $1\le T\le 10$；
• $2\le n\le 2\times 10^5$；
• $1\le A_i\le 10^6$。

每个测试点独立计分。