将序列的每个位置染成红色或蓝色。对于位置 $i$，若其左侧存在与它同色的位置，则令 $j$ 为其中离 $i$ 最近的位置；否则该位置的贡献为 $0$。

当 $j$ 存在时，位置 $i$ 的贡献定义为

$$\operatorname{contrib}(i)=\begin{cases}A_i,&A_i=A_j,\\0,&A_i\ne A_j.\end{cases}$$

求所有位置贡献之和的最大值。

输入格式

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

每组数据的第一行包含一个整数 $n$，第二行包含 $n$ 个整数 $A_1,A_2,\dots,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\leq T\leq 10$，$2\leq n\leq 2\times 10^5$，$1\leq A_i\leq 10^6$。

测试点	$n$	$A_i$
$1\sim 4$	$\leq 15$
$5\sim 7$	$\leq 10^2$
$8\sim 10$	$\leq 2000$
$11,12$	$\leq 2\times 10^4$	$\leq 10^6$
$13\sim 15$	$\leq 2\times 10^5$	$\leq 10$
$16\sim 20$		$\leq 10^6$

来源与数据说明

原题页面。以上题意为重新整理的表述，规则、输入输出和约束与原题一致。本题使用独立生成的训练数据，原题测试点表仅说明原比赛范围与特殊性质，本包评分不复刻官方测试点分布。标准输入输出，不要求文件读写。