Беси сортирует массив целых чисел собственным алгоритмом.
У неё есть куча из \(N\) \((1 \leq N \leq 2\cdot 10^5)\) целых чисел \(a_1,a_2,\dots,a_N\)
\((1 \leq a_i \leq 10^{11})\), которые она хочет перенести в другой массив в
отсортированном порядке.
Она постоянно ищет минимальный элемент в куче, удаляет его и добавляет
в конец массива. Беси требуется \(p\) секунд, чтобы найти минимальный элемент
в куче из \(p\) целых чисел.
ФД выделил Беси в помощь неограниченное количество коров.
Беси использует их следующим образом. Она разделила все свои целые числа
на две кучи: куча Беси и куча Помощниц. Для каждого числа в своей куче она
выполняет алгоритм как обычно. Для каждого целого числа в куче Помощниц
Беси назначает его отдельной корове. И предлагает ей поступать так.
Когда корова помощница получает число \(a_i\), она должна подождать \(a_i\)
секунд и затем добавить это число в конец массива. Если Беси и корова-помощница
добавляют число в одно и то же время, то сначала добавляется число Беси.
Если нескольким коровам-помощницам было дано одно и то же число,
они добавляют копии этого числа в одно и то же время.
Помогите Беси поделить её числа так, чтобы финальный массив был отсортирован,
а время сортировки было минимально.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит число
\(T\), количество независимых подтестов.
(
\(1\le T\le 10\)).
Каждый подтест имеет такую структуру:
Первая строка содержит \(N\) - количество целых чисел в массиве Беси.
Следующая строка содержит \(a_1, a_2, \dots, a_N\), - целые числа, которые
сортирует Беси. Некоторые целые числа могут появится множество раз.
Гарантируется, что сумма всех \(N\) по всем подтестам не превысит \(2\cdot 10^5\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждого подтеста выведите в отдельной строке минимальное время
сортировки массива, если Беси поделит числа оптимально.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
6
15
5
6
|