Live top-k total: hints, no solution

A control room keeps a live score tracker for response teams. It receives a sequence of events as a list of integers. A positive number v records a new team score of v; every score stays in the tracker forever and the same value can be recorded many times. The number 0 is a request for a report.

At each report, compute the sum of the k highest scores recorded so far; if fewer than k scores exist, sum all of them, and if none exist the sum is 0. Return the sums for all reports, in the order the reports were requested. The event list can be long and reports frequent, so re-sorting all scores for each report is too slow.

Examples

Input

k = 2, events = [5, 3, 0, 9, 0, 4, 0]

Output

[8, 14, 14]

Note

Reports see scores {5, 3}, then {5, 3, 9}, then {5, 3, 9, 4}: the top two sum to 8, 14 and 14.

Input

k = 3, events = [7, 0, 1, 0]

Output

[7, 8]

Note

With fewer than three scores, everything is summed.

Constraints

• 1 <= k <= 1000
• 0 <= number of events <= 60000, at most 6000 of them reports
• Every recorded score is an integer from 1 to 10000

Hint 1: a nudge

Between two reports, which scores can never matter again for the top k, however many more scores arrive?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing