D. Dragon These Nuts
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Cindy has been playing the new Pokemon game, and she's having a great time! Her team consists of five Dragon-type Pokemon (because she thinks they look awesome!), as well as her favorite Pokemon Magumaggu (the Lava Pokemon), the pre-evolution of Magcargo.

The latest entry in the Pokemon franchise contains several cooking minigames, where Cindy can prepare meals for her Pokemon to eat. In one cooking minigame, there are $$$n$$$ almonds, labeled $$$1$$$ to $$$n$$$, which her Magumaggu must roast. The $$$i$$$th almond must be roasted at least $$$a_i$$$ times. At the start of the minigame, the almonds are placed in a row in some random order. In one breath, Magumaggu can do the following:

  • Choose a subsegment of $$$k$$$ consecutive chestnuts and hit them with its fire breath; all chestnuts in this range get roasted once.
Let the power-point cost of this minigame be the minimum number of breaths needed to make each chestnut roasted its desired number of times. Help Cindy perform a worst case analysis—please provide any permutation of the $$$n$$$ almonds which maximizes the power-point cost of this minigame with those almonds.
Input

The first line of input contains a the two space-separated integers $$$n$$$ and $$$k$$$.

The second line of input contains $$$n$$$ space-separated integers $$$a_1, a_2, a_3, \dots, a_n$$$.

Output

Output a single line containing a permutation of the integers from $$$1$$$ to $$$n$$$ (separated by spaces), corresponding to a worst-case order in which the almonds should be placed (from left to right). If there are multiple possible solutions, any will be accepted.

Scoring

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq k \leq n \leq 2 \times 10^5 \\ \text{$1 \leq a_i \leq 10^9$ for each $i$.} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{40} & n \leq 5 \\ \hline 2 & \mathbf{40} & \text{$a_i \leq 2$ for each $i$} \\ \hline 3 & \mathbf{5} & \text{$a_i \leq 2023$ for each $i$} \\ \hline 4 & \mathbf{15} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Example
Input
5 3
7 77 2 22 222
Output
5 4 3 2 1
Note

For the sample test case, the proposed solution would have the almonds' values in the order $$$[222, 22, 2, 77, 7]$$$.

(Translator's Note): Magumaggu is only a transliteration of the Japanese name of the pre-evolution of Magcargo.