Bessie muốn sắp xếp mảng số nguyên bằng thuật toán riêng. Cô có một đống $N$ số $a_1,a_2,\dots,a_N$, với $(1 \leq N \leq 2\cdot 10^5)$ và $(1 \leq a_i \leq 10^{11})$, sẽ đưa vào mảng khác theo thứ tự đã sắp xếp. Cô liên tục tìm số nhỏ nhất trong đống, lấy ra và thêm vào cuối mảng. Tìm số nhỏ nhất giữa $p$ số mất $p$ giây.

Farmer John nhờ những con bò khác giúp, nhưng chúng lười, nên Bessie tận dụng điều đó. Cô chia các số thành đống của mình và đống trợ giúp. Cô xử lý đống mình như thường lệ, còn mỗi số trong đống kia được giao cho một bò trợ giúp khác nhau. Trang trại lớn nên cô có thể có bao nhiêu trợ giúp tùy ý. Bò nhận $a_i$ phải ngủ $a_i$ giây rồi thêm số vào cuối mảng ngay khi thức dậy. Nếu Bessie và bò trợ giúp thêm cùng lúc, số của Bessie được thêm trước vì cô là người lãnh đạo. Nhiều bò nhận cùng một số sẽ thêm các bản sao của số đó cùng lúc.

Hãy chia các số để mảng cuối được sắp xếp và thời gian sắp xếp là nhỏ nhất.

Dữ liệu vào

Dòng đầu chứa $T$, số bộ kiểm thử độc lập ($1\le T\le 10$).

Mỗi bộ có định dạng sau:

Dòng đầu chứa số lượng số nguyên $N$ trong mảng của Bessie.

Dòng tiếp theo chứa các số cần sắp xếp $a_1, a_2, \dots, a_N$. Một số có thể xuất hiện nhiều lần.

Đảm bảo tổng $N$ trên mọi bộ không vượt quá $2\cdot 10^5$.

Dữ liệu ra

Với mỗi bộ, in thời gian sắp xếp nhỏ nhất khi chia tối ưu trên một dòng mới.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

6
15
5
6

Ghi chú

Trong ví dụ đầu, cô có thể giao $1,2$ cho trợ giúp và giữ $4,5,10^{11}$.

Trong ví dụ thứ hai, tốt nhất là tự sắp xếp tất cả. Giao $4$ cho trợ giúp và giữ phần còn lại không được: Bessie sẽ thêm $17$ trước khi trợ giúp thêm $4$.

Trong ví dụ thứ ba, cô có thể giao tất cả cho trợ giúp.

Trong ví dụ thứ tư, cô có thể giao $1,4,5$ cho trợ giúp và giữ $2,5,100$.

Nhiệm vụ con

• Dữ liệu 2: $N\le 16$
• Dữ liệu 3–5: $N\le 150$
• Dữ liệu 6–8: $\sum N\le 5000$
• Dữ liệu 9–11: không có ràng buộc bổ sung.

Tác giả bài toán: Suhas Nagar