当前没有测试数据。

本题暂未上传测试数据，目前仅供阅读与练习。

本站练习请使用标准输入/输出；原卷中的文件名仅作原始资料参考。

题目描述

给定长度为 $n$ 的正整数数组 $A$，从左到右排成一排。将每个数染成红色或蓝色之一，按如下方式定义数组 $C$：

• 若 $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,\ldots,A_n$。

输出格式

每组数据输出一个非负整数，表示最终得分的最大值。

样例 1

输入

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

输出

1
0
8

数据范围

$1\le T\le10$，$2\le n\le2\times10^5$，$1\le A_i\le10^6$。

原卷完整题面

以下保留原卷的图示、完整样例解释、分档约束和特殊性质，便于核对。原卷中引用的外部样例文件未随本次题面上传。

下载原卷题面 PDF