Bessie will ein Ganzzahlarray mit ihrem eigenen Algorithmus sortieren. Sie hat einen Haufen aus $N$ Zahlen $a_1,a_2,\dots,a_N$ mit $(1 \leq N \leq 2\cdot 10^5)$ und $(1 \leq a_i \leq 10^{11})$, die sie sortiert in ein separates Array einfügt. Wiederholt sucht sie das Minimum, entfernt es und fügt es am Arrayende an. Das Finden des Minimums unter $p$ Zahlen dauert $p$ Sekunden.
Farmer John wies andere Kühe an, ihr zu helfen. Sie sind jedoch faul, was Bessie ausnutzt. Sie teilt die Zahlen in ihren Haufen und den Helferinnenhaufen. Ihren Haufen bearbeitet sie wie üblich; jede Zahl des anderen gibt sie einer anderen Helferin. Die Farm ist groß, daher sind beliebig viele Helferinnen verfügbar. Eine Helferin mit Zahl $a_i$ soll $a_i$ Sekunden schlafen und ihre Zahl sofort beim Aufwachen am Arrayende anfügen. Fügt Bessie gleichzeitig mit einer Helferin an, kommt Bessies Zahl zuerst, weil sie die Anführerin ist. Mehrere Helferinnen mit derselben Zahl fügen gleichzeitig Kopien davon an.
Teile die Zahlen so auf, dass das fertige Array sortiert ist und die Sortierzeit minimal wird.
Eingabe
Die erste Zeile enthält $T$, die Anzahl unabhängiger Testfälle ($1\le T\le 10$).
Jeder Testfall hat folgendes Format:
Die erste Zeile enthält die Anzahl der Zahlen $N$ in Bessies Array.
Die nächste Zeile enthält die zu sortierenden Zahlen $a_1, a_2, \dots, a_N$. Zahlen dürfen mehrfach vorkommen.
Die Summe von $N$ über alle Testfälle ist höchstens $2\cdot 10^5$.
Ausgabe
Gib für jeden Testfall in einer neuen Zeile die minimale Sortierzeit bei optimaler Aufteilung aus.
Beispiele
Eingabe 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
Ausgabe 1
6 15 5 6
Hinweis
Im ersten Beispiel kann Bessie $1,2$ den Helferinnen geben und $4,5,10^{11}$ behalten.
| Zeit | Ereignis |
|---|---|
| 1 | Helferin fügt an 1 |
| 2 | Helferin fügt an 2 |
| 3 | Bessie fügt an 4 |
| 5 | Bessie fügt an 5 |
| 6 | Bessie fügt an $10^{11}$ |
Im zweiten Beispiel ist es am besten, alles selbst zu sortieren. $4$ einer Helferin zu geben und den Rest zu behalten funktioniert nicht: Bessie fügt $17$ an, bevor die Helferin $4$ anfügt.
Im dritten Beispiel kann sie alle Zahlen den Helferinnen geben.
Im vierten Beispiel kann sie $1,4,5$ den Helferinnen geben und $2,5,100$ behalten.
| Zeit | Ereignis |
|---|---|
| 1 | Helferin fügt an 1 |
| 3 | Bessie fügt an 2 |
| 4 | Helferin fügt an 4 |
| 5 | Bessie fügt an 5 |
| 5 | Helferin fügt an 5 |
| 6 | Bessie fügt an 100 |
Teilaufgaben
- Eingabe 2: $N\le 16$
- Eingaben 3–5: $N\le 150$
- Eingaben 6–8: $\sum N\le 5000$
- Eingaben 9–11: keine zusätzlichen Einschränkungen.
Aufgabenautor: Suhas Nagar