Sliding Moles Maximum Coins

In this problem, you are given a sliding window game where a sequence of moles with heights h_i appears. The game window has a fixed length \(l\) and the mole sequence \(T\) has length \(t\) (with \(l \le t\)). Initially, the left end of \(T\) is aligned with the left end of the window. At the beginning of the first second the window is fixed (i.e. the sequence does not move) and displays moles \(T[1..l]\). Starting from the second second, the whole sequence moves leftwards one unit per second: the leftmost mole leaves the window and a new mole enters on the right so that at any moment, the window contains exactly \(l\) moles. This continues until either the player ends the game at some second or the sequence stops moving when the right end of \(T\) aligns with the window's right end. Hence, the game lasts at most \(t-l+1\) seconds.

During each second the player is allowed to "hit" at most one mole that is visible in the window. When hitting a mole \(i\) (with current height \(h_i\)), the player gains \(h_i\) coins, and the mole's height decreases by \(1\) immediately. Note that a mole may be hit multiple times in different seconds as long as it is visible in the window; however, its reward decreases by \(1\) coin for each subsequent hit (i.e. the first hit gives \(h_i\), the second gives \(h_i-1\), the third gives \(h_i-2\), and so on).

Your task is: Given \(l\), \(t\) and the initial mole heights sequence \(T = [h_1, h_2, \dots, h_t]\), determine, for every possible ending time \(s = 1,2,\dots,t-l+1\) (i.e. if the game is stopped at the end of second \(s\)), the maximum total coins the player can obtain by optimally scheduling the hits.

Note on mole availability: The mole at position \(i\) appears in the window in consecutive seconds. It is visible in seconds \(s\) for which its index \(i\) satisfies \[ s \in [a_i, b_i], \] where \[ a_i = \max(1, i-l+1) \quad \text{and} \quad b_i = \min(i, t-l+1). \] Thus, the maximum number of times a mole \(i\) can be hit is \(b_i-a_i+1\) (and you obviously will not hit a mole more times than its current height makes sense to yield positive coins).

Hint: This problem can be modeled as a scheduling/allocation problem. Think of each possible hit as an "event" with a time window during which it can be scheduled. In particular, for mole \(i\) and its \(j\)th hit (\(1 \le j \le \min(b_i-a_i+1, h_i)\)), you can only schedule the hit in a time slot \(s\) satisfying \[ s \in [a_i+j-1, b_i]. \] The coin reward for that hit is \(h_i-j+1\). You have at most one hit per second, so if the game ends at second \(s\), you have \(s\) available hit opportunities. Using a min cost flow formulation on a directed acyclic graph with nodes representing time slots is one standard approach.

inputFormat

The first line contains two integers \(l\) and \(t\) (\(1 \le l \le t\)), representing the game window length and the length of the mole sequence.

The second line contains \(t\) space-separated positive integers \(h_1, h_2, \dots, h_t\) representing the initial height (and coin value) of each mole.

outputFormat

Output \(t-l+1\) integers separated by spaces. The \(s\)th integer should be the maximum coins that can be obtained if the game is ended at second \(s\) (i.e. if exactly \(s\) hits, scheduled optimally, are allowed).

sample

3 5
3 2 4 1 5

3 5 12