URI Online Judge | 1055

Elegante Suma Permutada

Por Sohel Hafiz Bangladesh*

Timelimit: 1

Te será entregados n enteros A1A2A3...An. Encontrar una permutación de estos n enteros de modo que se maximice la suma de las diferencias absolutas entre elementos adyacentes.

Suponga n = 4 y los enteros dados son 4 2 1 5. La permutación 2 5 1 4 produce la suma máxima. Para esta permutación sum = abs(2-5) + abs(5-1) + abs(1-4) = 3+4+3 = 10.

De todas las 24 permutaciones, no obtendrá ninguna suma cuyo valor exceda 10. Llamaremos a este valor, 10, la elegante suma permutada..

Entrada

La primera línea de entrada es un entero T (T < 100) que representa el número de casos de prueba. Cada caso consiste en una línea que comienza con n (1 < n < 51) seguido de n enteros no negativos separados por un solo espacio. Ninguno de los elementos de la permutación dada excederá de 1000.

Salida

Para cada caso, muestre el número de caso seguido de la Elegante suma permutada..

Ejemplo de entrada Ejemplo de salida

3
4 4 2 1 5
4 1 1 1 1
2 10 1

Case 1: 10
Case 2: 0
Case 3: 9