P9780 [HUSTFC 2023] Azur Lane

You are a commander in the port area. You can strengthen your fleet by training “Commander Meowfficer”, which are trained from the corresponding “Meow Boxes”. Meow Boxes have $k$ levels; the higher the level, the rarer it is. Every day you will obtain some Meow Boxes (at least one), and then use “One-click Insert” to put these Meow Boxes into the “Meow Nest” for training. “One-click Insert” will put rarer Meow Boxes first (that is, after sorting by rarity from high to low, insert them one by one). The inserted Meow Boxes will be placed after the boxes that are already in the nest. At the **end of each day**, the system will automatically deduct an amount of money equal to the number of Meow Boxes currently in the Meow Nest. At the beginning, there are no Meow Boxes in your Meow Nest. Because you are very lazy, you will wait until after $n$ days to open all the Meow Boxes together. When you enter the Meow Nest after $n$ days, you see $m$ Meow Boxes. Use a sequence $a$ of length $m$ to represent the levels of the Meow Boxes in the Meow Nest, ordered by the time they were inserted. However, you have already forgotten how many Meow Boxes you obtained each day during these $n$ days, and you even forgot what $n$ was. Clearly, there are many possible situations. You want to know: for every integer $n$ satisfying $1 \leq n \leq m$, among all possible situations, what is the minimum total amount of money that could have been deducted over these $n$ days?

The first line contains two integers $m\ (1 \leq m \leq 10^6)$ and $k\ (1 \leq k \leq 10^6)$, representing the number of Meow Boxes in the Meow Nest and the maximum level of Meow Boxes, respectively. The second line contains $m$ integers $a_{1}, a_{2}, \ldots, a_{m}\ (1 \leq a_i \leq k)$, representing the levels of the Meow Boxes arranged in the Meow Nest.

Output one line with $m$ integers separated by spaces. The $i$-th integer represents, when $n=i$, the minimum total amount of money that could be deducted among all possible situations. If there is no valid situation, output $-1$.

Explanation for Sample 1: When $n=1$, it is impossible to obtain these $3$ Meow Boxes within one day (the level of the second Meow Box is greater than the level of the first Meow Box, which does not follow the rule that “One-click Insert” inserts from high to low), so output $-1$. When $n=2$, on the first day you obtain the first Meow Box; at this time there is $1$ Meow Box in the Meow Nest, so the cost for that day is $1$. On the second day you obtain the last two Meow Boxes; at this time there are $3$ Meow Boxes in the Meow Nest, so the cost for that day is $3$. Therefore, the total amount of money is $4$. When $n=3$, each day you obtain one Meow Box in order, and the total amount of money is $1+2+3=6$. Translated by ChatGPT 5