Кевин раньше попадал в воспоминания Рио, и в воспоминаниях Рио когда-то проводились серии соревнований. Кевин помнит всех участников и все задачи соревнований того времени, но он забыл конкретные раунды, распределение задач и точные рейтинги.
Всего есть \( m \) задач, при этом \( i \)-я задача имеет сложность \( b_i \). Пусть каждое соревнование состоит из \( k \) задач, в результате чего получается \( \lfloor \frac{m}{k} \rfloor \) соревнований. Это означает, что вы выбираете \( \lfloor \frac{m}{k} \rfloor \cdot k \) задач для соревнований в любом сочетании, при этом каждая задача выбирается не более одного раза, а оставшиеся \(m\bmod k\) задач остаются неиспользованными. Например, если \(m = 17\) и \(k = 3\), вы должны создать ровно \(5\) соревнований, состоящих из \(3\) задач каждое, и ровно \(2\) задачи останутся неиспользованными.
В соревнованиях участвовало всего \( n \) участников, причем Кевин был \(1\)-м участником. У \( i \)-го участника рейтинг \( a_i \). Во время соревнований участник решает все задачи, сложность которых не превышает его рейтинг, то есть \( i \)-й участник решает \( j \)-ю задачу тогда и только тогда, когда \( a_i \geq b_j \). В каждом соревновании ранг Кевина равен одному плюс количеству участников, которые решают больше задач, чем он.
Для каждого \( k = 1, 2, \ldots, m \) Кевин хочет знать минимальную сумму его рангов по всем \( \lfloor \frac{m}{k} \rfloor \) соревнованиям. Другими словами, для некоторого значения \(k\), после выбора задач для каждого соревнования, вы вычисляете ранг Кевина в каждом соревновании и суммируете эти ранги по всем \( \lfloor \frac{m}{k} \rfloor \) соревнованиям. Ваша цель — минимизировать это значение.
Обратите внимание, что соревнования для разных значений \(k\) независимы. Это означает, что для разных значений \(k\) вы можете независимо выбирать распределение задач в соревнованиях.
Выходные данные
Для каждого набора выведите \(m\) целых чисел — минимальную сумму рангов Кевина для каждого \( k = 1, 2, \ldots, m\).
Примечание
Для первого набора:
Когда \(k=1\), поскольку каждое соревнование содержит только одну задачу, распределение на самом деле уникально. Например, в соревновании, которое включает только третью задачу (которая имеет сложность \(4\)), все участники, кроме \(2\)-го, могут ее решить. Поскольку никто не решает строго больше задач, чем Кевин, его ранг в этом соревновании равен \(1\). Аналогично, в всех \(4\) соревнованиях ранги Кевина равны \(1,3,1,2\), и сумма равна \(7\).
Когда \(k=2\), один из оптимальных способов — выбрать \(1\)-ю и \(3\)-ю задачи для формирования одного соревнования, а \(2\)-ю и \(4\)-ю — для другого. В первом соревновании \(4\) участника соответственно решают \(2,1,2,2\) задачи, поэтому ранг Кевина равен \(1\); во втором они соответственно решают \(0,0,2,1\), поскольку \(2\) участника (\(3\)-й и \(4\)-й) решают больше задач, чем Кевин, его ранг равен \(1+2=3\). Таким образом, ответ равен \(1+3=4\). Можно доказать, что нет способа достичь меньшей суммы.
Когда \(k=3\), мы можем просто выбрать \(1\)-ю, \(3\)-ю и \(4\)-ю задачи, чтобы сделать соревнование, и ранг Кевина равен \(2\), что является оптимальным.
Когда \(k=4\), поскольку есть только одно соревнование, распределение также уникально, и ранг Кевина равен \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4 4
4 3 7 5
2 5 4 6
5 5
5 0 4 8 6
1 3 9 2 7
6 7
1 1 4 5 1 4
1 9 1 9 8 1 0
7 6
1 9 1 9 8 1 0
1 1 4 5 1 4
|
7 4 2 3
6 2 1 1 2
7 3 2 1 1 1 1
15 9 5 4 4 4
|