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