El Santi ha vist el servidor d'IA que ha fet el Marc i, com que tampoc té els 20.000 euros que costa actualment una tarja de 16GB de RAM, no pot finançar la millora que caldria. Ara bé, el que no li agrada es haver de minimitzar la capacitat total de transmissió per estalviar energia. Ha parlat amb un conegut expert de l'assessoria energètica i li ha promès un estalvi molt important en la factura de la llum. Santi sospita que el que farà realment aquest assessor serà punxar la llum del veí, però com que vol veure feliç al Marc amb la seva nova joguina, ha decidit contractar-lo. A més, li ha portat un munt de servidors antics que tenia al garatge de casa seva acumulant pols i ara poden connectar fins a 20 servidors.

Recordem que el Marc havia connectat 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 maximitza la capacitat total de transmissió de tota la línia.

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 (massa baix!)

• 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 ✓ (òptim!)

• 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é òptim!)

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 20) indicant el nombre de servidors
• Segona línia: N números enters entre 1 i 10^9, representant les capacitats dels servidors

Sortida

Per cada cas de prova, dues línies:

1. La capacitat total màxima 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

9
[2, 7, 8]
6
[1, 2, 3, 4]
20
[5, 5, 5, 5, 5]
25
[2, 3, 5, 7, 8, 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 quatre ordenacions, [2, 7, 8] és la que és més petita.