{"raw_statement":[{"iden":"statement","content":"你是港区的一位指挥官，你可以通过培养指挥喵来增强舰队的实力，指挥喵由对应的喵箱培育。喵箱有 $k$ 个等级，等级越高稀有度越高。你每天会获得若干个喵箱（至少一个），然后再使用 ''一键放入'' 将这些喵箱放到喵窝里进行培育。''一键放入'' 会优先放入稀有度更高的喵箱（即按照稀有度从高到低排序后依次放入），放入的喵箱会排在已放入喵箱的后面，在**每天结束时**系统会自动扣除与喵窝中喵箱数量相等的钱。最开始时你的喵窝里没有喵箱。\n\n因为你非常懒，所以你会等 $n$ 天后才把喵箱一起打开。在你 $n$ 天后进入喵窝时，你看到了 $m$ 个喵箱，用一个长度为 $m$ 的序列 $a$ 表示喵窝里按放入先后顺序排列的喵箱的等级。但是你已经忘了这 $n$ 天里你每天获得了多少喵箱了，你甚至忘了 $n$ 的值是多少，显然这有许多情况。你想知道，对于满足 $1 \\leq n \\leq m$ 的所有整数 $n$，在所有情况中，这 $n$ 天总共扣除的钱数至少为多少？"},{"iden":"input","content":"第一行包含两个整数 $m\\ (1 \\leq m \\leq 10^6)$，$k\\ (1 \\leq k \\leq 10^6)$，分别表示喵窝中喵箱的数量和喵箱的最高等级。\n\n第二行包含 $m$ 个整数 $a_{1}, a_{2}, \\ldots, a_{m}\\ (1 \\leq a_i \\leq k)$，表示喵窝中排列着的喵箱的等级。\n\n"},{"iden":"output","content":"输出一行用空格间隔的 $m$ 个整数，其中第 $i$ 个整数表示当 $n=i$ 时在所有可能的情况下至少会扣除的钱数。如果没有合法的情况，请输出 $-1$。\n\n"},{"iden":"note","content":"样例一解释：\n\n当 $n=1$ 时，无法在一天内获得这 $3$ 个喵箱（第二个喵箱的等级大于第一个喵箱的等级，不符合 ``一键放入'' 从高到低放入的原则），因此输出 $-1$。\n\n当 $n=2$ 时，第一天获得第一个喵箱，此时喵窝内有 $1$ 个喵箱，当天花费为 $1$；第二天获得后两个喵箱，此时喵窝内有 $3$ 个喵箱，当天花费为 $3$。因此总钱数为 $4$。\n\n当 $n=3$ 时，每天依次获得一个喵箱，总钱数为 $1+2+3=6$。"}],"translated_statement":null,"sample_group":[["3 3\n2 3 1\n","-1 4 6 "],["8 4\n3 2 4 2 1 2 3 2\n","-1 -1 -1 21 22 25 29 36 "]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}