Bessie intenta ordenar un arreglo de enteros con su propio algoritmo. Tiene un montón de $N$ enteros $a_1,a_2,\dots,a_N$, con $(1 \leq N \leq 2\cdot 10^5)$ y $(1 \leq a_i \leq 10^{11})$, que colocará ordenados en otro arreglo. Repetidamente encuentra el mínimo del montón, lo retira y lo añade al final del arreglo. Encontrar el mínimo entre $p$ enteros le lleva $p$ segundos.
Farmer John pidió a otras vacas que la ayudaran, pero son perezosas, y Bessie lo aprovecha. Divide los enteros en su montón y el de las ayudantes. Procesa el suyo normalmente y asigna cada entero del otro a una ayudante distinta. La granja es grande, así que puede tener tantas ayudantes como quiera. Una ayudante que recibe $a_i$ duerme $a_i$ segundos y añade su entero al final del arreglo inmediatamente al despertar. Si Bessie y una ayudante añaden a la vez, el entero de Bessie va primero porque es la líder. Varias ayudantes que reciben el mismo entero añaden copias simultáneamente.
Divide los enteros de modo que el arreglo final quede ordenado y el tiempo de ordenación sea mínimo.
Entrada
La primera línea contiene $T$, el número de casos independientes ($1\le T\le 10$).
Cada caso tiene este formato:
La primera línea contiene el número de enteros $N$ del arreglo de Bessie.
La siguiente contiene los enteros a ordenar, $a_1, a_2, \dots, a_N$. El mismo entero puede aparecer varias veces.
La suma de $N$ sobre todos los casos no supera $2\cdot 10^5$.
Salida
Para cada caso, imprime en una línea nueva el tiempo mínimo de ordenación con una división óptima.
Ejemplos
Entrada 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
Salida 1
6 15 5 6
Nota
En el primer ejemplo puede asignar $1,2$ a las ayudantes y quedarse con $4,5,10^{11}$.
| Tiempo | Evento |
|---|---|
| 1 | La ayudante añade 1 |
| 2 | La ayudante añade 2 |
| 3 | Bessie añade 4 |
| 5 | Bessie añade 5 |
| 6 | Bessie añade $10^{11}$ |
En el segundo, lo mejor es ordenar todo ella misma. Asignar $4$ a una ayudante y quedarse con el resto no funciona: Bessie añadiría $17$ antes de que la ayudante añadiera $4$.
En el tercero puede asignar todos los enteros a las ayudantes.
En el cuarto puede asignar $1,4,5$ a las ayudantes y quedarse con $2,5,100$.
| Tiempo | Evento |
|---|---|
| 1 | La ayudante añade 1 |
| 3 | Bessie añade 2 |
| 4 | La ayudante añade 4 |
| 5 | Bessie añade 5 |
| 5 | La ayudante añade 5 |
| 6 | Bessie añade 100 |
Subtareas
- Entrada 2: $N\le 16$
- Entradas 3–5: $N\le 150$
- Entradas 6–8: $\sum N\le 5000$
- Entradas 9–11: sin restricciones adicionales.
Autor del problema: Suhas Nagar