「HGOI-1」Mole

在长度为 $l$ 的游戏窗口上，有一个长为 $t$ 的地鼠序列 $(l \le t)$，初始序列左端与窗口左端对齐，接下来序列每秒移动一个单位长度，（即最左端的地鼠离开窗口，最右端的地鼠进入窗口），向左滚动直至玩家结束游戏或者序列最右端与窗口最右端重合（即任何时刻窗口内均应有 $l$ 只地鼠）。 游戏开始的第一秒序列不会移动，不难发现游戏最多会进行 $(t-l+1)$ 秒。 序列 $T$ 中的每一只地鼠都有自己的高度 $h_i$，玩家每次可以选择击打一只地鼠，玩家可以获得与地鼠高度 $h_i$ 数值相同的金币奖励，同时地鼠 $i$ 的高度 $h_i$ 会减一。 经过调研，$\text{brealid}$ 控制了游戏运行速度，使得玩家在地鼠序列移动一个单位长度的同时**最多只能打击一次**（也可以不打）。 现在 $\text{brealid}$ 告诉了你某一次游戏的窗口长度 $l$、序列长度 $t$ 以及某一局游戏中生成的地鼠高度序列 $T$。我们可爱的 $\text{brealid}$ 想要知道，她在**任意时刻**结束游戏所能得到的**最多金币**，即在第 $1,2,\cdots (t-l+1)$ 秒时停止游戏分别可以获得的最多金币。 ## Input 第一行两个整数 $l$，$t$，表示窗口长度 $l$ 和序列长度 $t$。 第二行 $t$ 个整数，表示某一局中的地鼠高度序列。 ## Output 一行 $t-l+1$ 个整数 $a_1,a_2,\cdots a_{t-l+1}$，$a_i$ 表示第 $i$ 秒时结束游戏可以获得的最多的金币数。 [samples] ## Background $\text{brealid}$ 觉得普通的打地鼠游戏太过于 $\text{simple}$ 了。所以，她设计了一款全新的打地鼠游戏。 ## Note #### 样例解释 第一秒：锤 $2$，答案加 $3$。 第二秒：锤 $2$，答案加 $2$。 第三秒：随便锤一个，答案加 $1$。 第四秒：再随便锤一个（非 $0$ 的），答案加 $1$。 第五秒：锤 $9$，答案加 $5$。 第六秒：锤 $9$，答案加 $4$。 #### 数据范围 本题采用**捆绑测试**，共有 $4$ 个 $\text{subtask}$，最终分数为所有 $\text{subtask}$ 分数之和。 $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{Task} & \textbf{Score} & l\le t\le \cr\hline 1 & 10 & 10 \cr\hline 2 & 20 & 500 \cr\hline 3 & 30 & 5000 \cr\hline 4 & 40 & 10^6 \cr\hline \end{array} $$ 对于 $100\%$ 的数据，$1\le l\le t\le 10^6$，$|h_i|\le 10^9$。