Sắp Xếp Ngủ

Bessie sắp xếp một mảng bằng cách liên tục tìm phần tử nhỏ nhất, loại bỏ nó, và thêm vào mảng kết quả. Tìm phần tử nhỏ nhất trong đống $p$ số nguyên mất $p$ giây.

Bessie có thể chia các số nguyên giữa mình và các con bò trợ giúp:

• Bessie xử lý đống của mình bình thường (mỗi lần rút mất thời gian bằng kích thước đống hiện tại).
• Trợ giúp được giao một số nguyên thì sẽ ngủ đúng bằng giá trị số đó (tính bằng giây), rồi thêm nó vào mảng kết quả khi thức dậy.
• Nếu Bessie và trợ giúp hoàn thành cùng lúc, phần tử của Bessie được thêm trước.

Hãy tìm thời gian tối thiểu để sắp xếp mảng bằng cách phân chia tối ưu.

Dữ liệu vào

• Dòng đầu tiên: số nguyên $T$ ($1\le T\le 10$) - số test case.
• Mỗi test case:
  • Dòng 1: số nguyên $N$ ($1\le N\le 2\times {10}^5$).
  • Dòng 2: $N$ số nguyên $a_1,\dots ,a_N$ ($1\le a_i\le {10}^{11}$).
• Tổng $N$ qua tất cả test case $\le 2\times {10}^5$.

Dữ liệu ra

Với mỗi test case, in thời gian tối thiểu.

Ràng buộc

• $1\le T\le 10$
• $1\le N\le 2\times {10}^5$
• $1\le a_i\le {10}^{11}$

Ví dụ