Juego de Cooperación
Las competencias atléticas en las escuelas algunas veces se vuelven muy controversiales y competitivas. Para promover el trabajo en equipo, los profesores han creado un juego donde la cooperación lleva a obtener mejores puntuaciones. Este juego comienza con estudiantes parados en una línea. Para obtener una puntuación, dos estudiantes de la misma aula saldrán de la línea. Si ellos eran los estudiantes número y , añaden a la puntuación total. Los lugares vacíos de los dos estudiantes que acaban de salir serán compactados. El juego finaliza cuando no hay más pares de estudiantes de la misma aula. Por ejemplo, considera seis estudiantes inicialmente parados en una línea: Los números son los números de las aulas de los estudiantes. Si los estudiantes salen de la línea en el orden: aula número 1, luego aula número 2, luego aula número 3, la puntuación total es 5 + 3 + 1 = 9. Sin embargo, en la misma situación inicial, si los estudiantes salen de la línea en el orden 3, 2, 1, entonces la puntuación total es 1 + 1 + 1 = 3. Dados los números de las aulas en la línea inicial, escribe un programa que calcule la mayor puntuación posible.
Entrada
La primera línea contiene un entero , el número de casos de prueba (). Los casos de prueba siguen: La primera línea de cada caso contiene un entero , el número de estudiantes (). En la siguiente línea aparecen los números de las aulas. Los números de las aulas son enteros desde hasta . La suma de sobre todos los casos no excede .
Salida
Para cada caso de prueba, imprime una línea con un entero: la mayor puntuación posible.
Subtareas
Subtarea 1 (10 puntos): Todos los estudiantes pertenecen a la misma aula.
Subtarea 2 (20 puntos): Los números de las aulas de los estudiantes están en orden ascendente.
Subtarea 3 (20 puntos): Para cada aula, hay exactamente dos estudiantes pertenecientes a ella. es par.
Subtarea 4 (25 puntos): . La suma de sobre todos los casos no excede 5000.
Subtarea 5 (25 puntos): Sin restricciones adicionales.
Ejemplos de entrada y salida
Entrada 1
2
7
1 2 1 1 2 1 2
12
1 2 3 1 2 3 1 2 3 1 2 3
Salida 1
10
30
Comments