Bessie tenta ordenar um vetor de inteiros com seu próprio algoritmo. Tem uma pilha de $N$ inteiros $a_1,a_2,\dots,a_N$, com $(1 \leq N \leq 2\cdot 10^5)$ e $(1 \leq a_i \leq 10^{11})$, que colocará ordenados em outro vetor. Repetidamente encontra o mínimo da pilha, retira-o e adiciona-o ao fim do vetor. Encontrar o mínimo entre $p$ inteiros leva $p$ segundos.

Farmer John pediu que outras vacas ajudassem, mas elas são preguiçosas, e Bessie aproveita isso. Divide os inteiros em sua pilha e a das ajudantes. Processa a sua normalmente e atribui cada inteiro da outra a uma ajudante diferente. A fazenda é grande, então pode ter quantas ajudantes quiser. Uma ajudante que recebe $a_i$ dorme $a_i$ segundos e adiciona seu inteiro ao fim do vetor imediatamente ao acordar. Se Bessie e uma ajudante adicionam ao mesmo tempo, o inteiro de Bessie vem primeiro, pois ela é a líder. Várias ajudantes com o mesmo inteiro adicionam cópias simultaneamente.

Divida os inteiros para que o vetor final esteja ordenado e o tempo de ordenação seja mínimo.

Entrada

A primeira linha contém $T$, o número de casos independentes ($1\le T\le 10$).

Cada caso tem o seguinte formato:

A primeira linha contém o número de inteiros $N$ no vetor de Bessie.

A próxima contém os inteiros a ordenar, $a_1, a_2, \dots, a_N$. Um mesmo inteiro pode aparecer várias vezes.

A soma de $N$ sobre todos os casos não excede $2\cdot 10^5$.

Saída

Para cada caso, imprima em uma nova linha o tempo mínimo de ordenação com divisão ótima.

Exemplos

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

Saída 1

6
15
5
6

Explicação

No primeiro exemplo, pode atribuir $1,2$ às ajudantes e ficar com $4,5,10^{11}$.

No segundo, o melhor é ordenar tudo sozinha. Atribuir $4$ a uma ajudante e ficar com o resto não funciona: Bessie adicionaria $17$ antes de a ajudante adicionar $4$.

No terceiro, pode atribuir todos os inteiros às ajudantes.

No quarto, pode atribuir $1,4,5$ às ajudantes e ficar com $2,5,100$.

Subtarefas

• Entrada 2: $N\le 16$
• Entradas 3–5: $N\le 150$
• Entradas 6–8: $\sum N\le 5000$
• Entradas 9–11: sem restrições adicionais.

Autor do problema: Suhas Nagar