El Marc vol crear un servidor d'IA i posar-li un Qwen. Com que no té els 20.000 euros que li costa actualment una tarja de 16GB de RAM, ha de connectar els seus vells servidors supermicro en una línia per distribuir la càrrega de treball. Cada servidor té una capacitat màxima de processar dades, però la connexió entre dos servidors adjacents només pot transmetre una quantitat limitada de dades igual al mínim de les capacitats dels dos servidors.

El problema és que els servidors ja estan físicament instal·lats en un ordre concret, però pots reordenar-los com vulguis abans de connectar-los. El teu objectiu és trobar l'ordre que minimitza la capacitat total de transmissió de tota la línia (per estalviar energia).

La capacitat total és la suma de totes les connexions entre servidors adjacents.

Per exemple:

• Si tens servidors [8, 2, 7] en aquest ordre, les connexions són:

  • Entre 8 i 2: min(8,2) = 2
  • Entre 2 i 7: min(2,7) = 2
  • Total: 2 + 2 = 4 ✓ (òptim!)

• Però si els reordenes com [8, 7, 2]:

  • Entre 8 i 7: min(8,7) = 7
  • Entre 7 i 2: min(7,2) = 2
  • Total: 7 + 2 = 9 (massa alt!)

• I si els poses com [2, 7, 8]:

  • Entre 2 i 7: min(2,7) = 2
  • Entre 7 i 8: min(7,8) = 7
  • Total: 2 + 7 = 9 (també massa alt!)

Entrada

La primera línia indica els casos de prova a considerar.

Per cada cas de prova:

• Primera línia: un nombre N (entre 2 i 8) indicant el nombre de servidors
• Segona línia: N números enters entre 1 i 200, representant les capacitats dels servidors

Sortida

Per cada cas de prova, dues línies:

1. La capacitat total mínima possible
2. L'ordenació més petita (de menor a major) que aconsegueix aquesta capacitat mínima (en format de llista estàndard)

Exemple d'Entrada

4
3
8 2 7
4
1 4 2 3
5
5 5 5 5 5
6
10 2 8 3 7 5

Exemple de Sortida

4
[7, 2, 8]
4
[2, 3, 1, 4]
20
[5, 5, 5, 5, 5]
15
[5, 7, 2, 8, 3, 10]

Explicació del Primer Cas

Servidors disponibles: [8, 2, 7]

Provem diferents ordenacions:

• [2, 7, 8]: min(2,7) + min(7,8) = 2 + 7 = 9
• [2, 8, 7]: min(2,8) + min(8,7) = 2 + 7 = 9
• [7, 2, 8]: min(7,2) + min(2,8) = 2 + 2 = 4 ✓
• [7, 8, 2]: min(7,8) + min(8,2) = 7 + 2 = 9
• [8, 2, 7]: min(8,2) + min(2,7) = 2 + 2 = 4 ✓
• [8, 7, 2]: min(8,7) + min(7,2) = 7 + 2 = 9

De les dues ordenacions, [7, 2, 8] és la que que comença per un nombre menor, per tant la més petita.