Bessie veut trier un tableau d’entiers avec son propre algorithme. Elle a un tas de $N$ entiers $a_1,a_2,\dots,a_N$, avec $(1 \leq N \leq 2\cdot 10^5)$ et $(1 \leq a_i \leq 10^{11})$, qu’elle placera dans un autre tableau dans l’ordre trié. Elle trouve répétitivement le minimum du tas, le retire et l’ajoute à la fin du tableau. Trouver le minimum parmi $p$ entiers lui prend $p$ secondes.

Farmer John a demandé à d’autres vaches de l’aider, mais elles sont paresseuses, et Bessie en profite. Elle sépare les entiers en son tas et le tas des assistantes. Elle traite son tas normalement et attribue chaque entier de l’autre tas à une assistante différente. La ferme étant grande, elle peut avoir autant d’assistantes que souhaité. Une assistante recevant $a_i$ doit dormir $a_i$ secondes puis ajouter immédiatement son entier à la fin du tableau à son réveil. Si Bessie et une assistante ajoutent simultanément, l’entier de Bessie vient d’abord, car elle dirige. Plusieurs assistantes recevant le même entier en ajoutent des copies simultanément.

Répartissez les entiers pour que le tableau final soit trié et que le temps de tri soit minimal.

Entrée

La première ligne contient $T$, le nombre de cas indépendants ($1\le T\le 10$).

Chaque cas a le format suivant :

Sa première ligne contient $N$, le nombre d’entiers du tableau de Bessie.

La ligne suivante contient les entiers à trier, $a_1, a_2, \dots, a_N$. Un même entier peut apparaître plusieurs fois.

La somme de $N$ sur tous les cas ne dépasse pas $2\cdot 10^5$.

Sortie

Pour chaque cas, affichez sur une nouvelle ligne le temps minimal de tri avec une répartition optimale.

Exemples

Entrée 1

4
5
1 2 4 5 100000000000
5
17 53 4 33 44
4
3 5 5 5
6
2 5 100 1 4 5

Sortie 1

6
15
5
6

Remarque

Dans le premier exemple, Bessie peut attribuer $1,2$ aux assistantes et garder $4,5,10^{11}$.

Dans le deuxième, le mieux est de tout trier elle-même. Attribuer $4$ à une assistante et garder le reste ne fonctionne pas : Bessie ajouterait $17$ avant que l’assistante n’ajoute $4$.

Dans le troisième exemple, elle peut tout attribuer aux assistantes.

Dans le quatrième, elle peut attribuer $1,4,5$ aux assistantes et garder $2,5,100$.

Sous-tâches

• Entrée 2 : $N\le 16$
• Entrées 3–5 : $N\le 150$
• Entrées 6–8 : $\sum N\le 5000$
• Entrées 9–11 : aucune contrainte supplémentaire.

Auteur du problème : Suhas Nagar