Поликарп тренирует свое умение решать задачи. У него есть список из \(n\) задач со сложностями \(a_1, a_2, \dots, a_n\) соответственно. Его план состоит в том, чтобы тренироваться ровно \(k\) дней. Каждый день он должен решать хотя бы одну задачу из своего списка. Поликарп решает задачи в том порядке, в котором они заданы в списке, и он не может пропустить какую-либо задачу из списка. Он должен решить ровно \(n\) задач ровно за \(k\) дней.
Таким образом, каждый день Поликарп решает последовательность подряд идущих (последовательных) задач с самого начала списка. Он не может пропускать задачи или решать их несколько раз. В итоге за \(k\) дней он решит \(n\) задач.
Полезность \(j\)-го дня тренировки Поликарпа равна максимальной сложности задачи среди всех задач, которые Поликарп решит в течение \(j\)-го дня (то есть если он решит задачи с номерами от \(l\) до \(r\) в течение какого-то дня, тогда полезность этого дня равна \(\max\limits_{l \le i \le r}a_i\)). Общая полезность его тренировки — это сумма полезностей по всем \(k\) дням его тренировки.
Вы хотите помочь Поликарпу получить максимально возможную общую полезность среди всех доступных способов решить задачи. Ваша задача — распределить \(n\) задач по \(k\) дням таким образом, что это распределение удовлетворяет ограничениям, описанным выше, и общая полезность является максимально возможной.
Например, если \(n = 8, k = 3\) и \(a = [5, 4, 2, 6, 5, 1, 9, 2]\), одним из возможных способов с максимальной общей полезностью является следующий: \([5, 4, 2], [6, 5], [1, 9, 2]\). Здесь общая полезность равна \(5 + 6 + 9 = 20\).
Выходные данные
В первой строке выведите максимально возможную общую полезность.
Во второй строке выведите \(k\) натуральных чисел \(t_1, t_2, \dots, t_k\) (\(t_1 + t_2 + \dots + t_k\) должно равняться \(n\)), где \(t_j\) равно количеству задач, которое Поликарп решит в \(j\)-й день, чтобы достигнуть максимальной общей полезности его тренировки.
Если существует несколько возможных решений, выведите любое из них.
Примечание
Первый тестовый пример описан в условии задачи.
Во втором тестовом примере только один способ распределить задачи из списка и только одна возможная общая полезность.
В третьем тестовом примере лучшим ответом является распределить задачи следующим образом: \([1, 2000], [2000, 2]\). Тогда суммарная полезность будет равна \(2000 + 2000 = 4000\).