Bessie רוצה למיין מערך שלמים באלגוריתם שלה. יש לה ערימה של $N$ מספרים $a_1,a_2,\dots,a_N$, עם $(1 \leq N \leq 2\cdot 10^5)$ ו־$(1 \leq a_i \leq 10^{11})$, שאותם תשים במערך נפרד בסדר ממוין. היא מוצאת שוב ושוב את המינימום בערימה, מסירה אותו ומוסיפה אותו לסוף המערך. מציאת המינימום בין $p$ מספרים אורכת $p$ שניות.

Farmer John הורה לפרות אחרות לעזור, אך הן עצלניות, ו־Bessie מנצלת זאת. היא מחלקת את המספרים לערימה שלה ולערימת העוזרות. את שלה היא מעבדת כרגיל, וכל מספר בערימה האחרת ניתן לעוזרת אחרת. החווה גדולה ולכן אפשר לקבל עוזרות רבות ככל שתרצה. עוזרת שמקבלת $a_i$ ישנה $a_i$ שניות ומוסיפה את המספר לסוף המערך מיד כשהיא מתעוררת. אם Bessie ועוזרת מוסיפות בו־זמנית, המספר של Bessie קודם כי היא המנהיגה. עוזרות שקיבלו אותו מספר מוסיפות עותקים שלו בו־זמנית.

חלקו את המספרים כך שהמערך הסופי יהיה ממוין וזמן המיון יהיה מזערי.

קלט

השורה הראשונה מכילה את $T$, מספר מקרי הבדיקה הבלתי תלויים ($1\le T\le 10$).

לכל מקרה הפורמט הבא:

השורה הראשונה מכילה את מספר השלמים $N$ במערך של Bessie.

השורה הבאה מכילה את השלמים למיון $a_1, a_2, \dots, a_N$. אותו מספר יכול להופיע פעמים אחדות.

מובטח שסכום $N$ על פני כל המקרים אינו עולה על $2\cdot 10^5$.

פלט

לכל מקרה הדפיסו בשורה חדשה את זמן המיון המזערי בחלוקה מיטבית.

דוגמאות

קלט 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

פלט 1

6
15
5
6

הערה

בדוגמה הראשונה אפשר לתת $1,2$ לעוזרות ולשמור $4,5,10^{11}$.

בשנייה, הכי טוב למיין הכול בעצמה. לתת $4$ לעוזרת ולשמור את השאר לא עובד: Bessie תוסיף $17$ לפני שהעוזרת תוסיף $4$.

בשלישית אפשר לתת את כל המספרים לעוזרות.

ברביעית אפשר לתת $1,4,5$ לעוזרות ולשמור $2,5,100$.

תתי־משימות

• קלט 2: $N\le 16$
• קלטים 3–5: $N\le 150$
• קלטים 6–8: $\sum N\le 5000$
• קלטים 9–11: ללא מגבלות נוספות.

מחבר הבעיה: Suhas Nagar