Commanding the Feline Fleet

You are the commander of the harbor zone. In order to strengthen your fleet you may cultivate command cats from cat boxes. There are \(k\) levels of cat boxes; a higher level represents a higher rarity. Every day you gain at least one cat box. Then, using the "One‐Click Deposit" feature, you deposit all the boxes obtained on that day into your cat house for cultivation. When depositing, the system sorts the boxes in descending order of rarity (i.e. boxes of a higher level are deposited first) and appends them to those already present in the cat house. At the end of each day, an amount of money equal to the number of boxes currently in the cat house is deducted from your account. Initially, your cat house is empty.

You are so lazy that you postpone opening the boxes until after several days. After some unknown number \(n\) of days you enter the cat house and find \(m\) boxes. The boxes appear in the order they were deposited and their levels are given by a sequence \(a\) of length \(m\) (from first to last deposited).

You have forgotten how many boxes you received each day, or even the value of \(n\). For every integer \(n\) with \(1 \le n \le m\) for which it is possible to have a valid scenario, determine the minimum total money deducted over the \(n\) days. If it is impossible to split the sequence into \(n\) days following the rule below, output -1 for that \(n\).

The deposition rule: When boxes are deposited in a day, the boxes obtained that day must appear in non‐increasing order (i.e. each day’s sequence, when considered by itself, is sorted in descending order). Note that if \(a_i < a_{i+1}\) then the boxes \(a_i\) and \(a_{i+1}\) must come from different days.

The cost for a given day is equal to the total number of boxes held at the end of that day. Hence, if the boxes obtained on day \(i\) is \(L_i\) (with \(L_i \ge 1\)) then the total deduction over \(n\) days is:

[ \text{Cost} = L_1 + (L_1+L_2) + \cdots + (L_1+L_2+\cdots+L_n) = \sum_{i=1}^{n} (n-i+1) L_i. ]

Your task is: For every \(n\) from 1 to \(m\), among all valid ways to partition the sequence \(a\) into \(n\) contiguous segments where each segment is non‐increasing, determine the minimum possible total deduction. (If no valid partition exists for a given \(n\), output -1.)

inputFormat

The first line contains two integers \(m\) and \(k\) (the number of boxes and the number of levels of boxes, respectively).

The second line contains \(m\) integers \(a_1, a_2, \dots, a_m\) where \(1 \le a_i \le k\) representing the levels of the boxes in the order they were deposited.

outputFormat

Output \(m\) space‐separated integers. The \(i\)th integer should be the minimum total money deducted over \(i\) days, or -1 if it is impossible to have a valid scenario with exactly \(i\) days.

sample

3 5
5 4 4

3 4 6