Person in Charge

• SleepingCup

Problem Description

Given a positive integer array $A$ of length $n$, where all numbers are arranged in a row from left to right.

You need to color each number in $A$ either red or blue, and then calculate the final score as follows:

Let $C$ be an integer array of length $n$. For each number $A_i$ in $A$ ($1 \le i \le n$):

• If there is no number to the left of $A_i$ with the same color, then $C_i = 0$.
• Otherwise, let $A_j$ be the closest number to the left of $A_i$ with the same color. If $A_i = A_j$, then $C_i = A_i$; otherwise, $C_i = 0$.

Your final score is the sum of all integers in $C$, i.e., $\sum \limits_{i=1}^n C_i$. You need to maximize the final score. Please determine the maximum possible final score.

Input Format

There are multiple test cases.

The first line of input contains a positive integer $T$, indicating the number of test cases.

This is followed by $T$ test cases, each formatted as follows:

The first line contains a positive integer $n$, indicating the length of the array.

The second line contains $n$ positive integers $A_1, A_2, \dots, A_n$, representing the elements of array $A$.

Output Format

For each test case: Output a line containing a non-negative integer, representing the maximum possible final score.

Samples

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

1
0
8

Sample 1 Explanation

For the first test case, here are three possible coloring schemes:

1. Color $A_1, A_2$ red and $A_3$ blue ($\red{1}\red{2}\blue{1}$). The score calculation is as follows:
   • For $A_1$, since there is no red number to its left, $C_1 = 0$.
   • For $A_2$, the closest red number to its left is $A_1$. Since $A_1 \neq A_2$, $C_2 = 0$.
   • For $A_3$, since there is no blue number to its left, $C_3 = 0$.
     The final score for this scheme is $C_1 + C_2 + C_3 = 0$.
2. Color $A_1, A_2, A_3$ all red ($\red{121}$). The score calculation is as follows:
   • For $A_1$, since there is no red number to its left, $C_1 = 0$.
   • For $A_2$, the closest red number to its left is $A_1$. Since $A_1 \neq A_2$, $C_2 = 0$.
   • For $A_3$, the closest red number to its left is $A_2$. Since $A_2 \neq A_3$, $C_3 = 0$.
     The final score for this scheme is $C_1 + C_2 + C_3 = 0$.
3. Color $A_1, A_3$ red and $A_2$ blue ($\red{1}\blue{2}\red{1}$). The score calculation is as follows:
   • For $A_1$, since there is no red number to its left, $C_1 = 0$.
   • For $A_2$, since there is no blue number to its left, $C_2 = 0$.
   • For $A_3$, the closest red number to its left is $A_1$. Since $A_1 = A_3$, $C_3 = A_3 = 1$.
     The final score for this scheme is $C_1 + C_2 + C_3 = 1$.

It can be proven that no coloring scheme yields a final score greater than $1$.

For the second test case, it can be proven that any coloring scheme results in a final score of $0$.

For the third test case, an optimal coloring scheme is to color $A_1, A_2, A_4, A_5, A_7$ red and $A_3, A_6, A_8$ blue ($\red{35}\blue{2}\red{51}\blue{2}\red{1}\blue{4}$). The corresponding $C = [0, 0, 0, 5, 0, 1, 2, 0]$, and the final score is $8$.

Sample 2

See the files color/color2.in and color/color2.ans in the contestant directory.

Data Range

For all test data, it is guaranteed that: $1\le T\le 10$, $2\le n\le 2\times 10^5$, $1\le A_i\le 10^6$.