تحاول 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$ لمساعدة والإبقاء على الباقي لا ينجح؛ لأنها ستضيف $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