P5101 [JOI 2017 Final] Rope / Rope

**This problem is translated from [JOI 2017 Final](https://www.ioi-jp.org/joi/2016/2017-ho/) T5 「[縄](https://www.ioi-jp.org/joi/2016/2017-ho/2017-ho.pdf) / [Rope](https://www.ioi-jp.org/joi/2016/2017-ho/2017-ho-en.pdf)」.** JOI is playing with a rope. The rope can be regarded as a line segment extending left and right with length $N$. The rope is made by connecting $N$ pieces of string. Each piece has length $1$ and thickness $1$. There are $M$ colors on the rope. The color of the $i$-th piece from the left $(1\leqslant i\leqslant N)$ is $C_i(1\leqslant C_i\leqslant M)$. The **left endpoint of the rope** means the left endpoint of the $1$-st piece from the left, and the **right endpoint of the rope** means the right endpoint of the $1$-st piece from the right. Clearly, the distance from the right endpoint of the $i$-th piece from the left $(1\leqslant i\leqslant N)$ to the left endpoint of the rope is $i$. JOI shortened the rope. More precisely, JOI repeatedly performs the following process until the rope length becomes $2$. - Suppose the current rope length is $L$. Choose an integer $j(1\leqslant j \Large\frac{L}{2}$, then twist the $i$-th piece from the left $(2j-L+1\leqslant i\leqslant j)$ together with the $(2j-i+1)$-th piece from the left. In this case, the original left endpoint of the rope becomes the right endpoint, and the rope length becomes $j$. - Two pieces can be twisted together only if they have the same color. Before twisting two pieces together, you may change their colors arbitrarily. The cost to dye a piece into another color is equal to the thickness of that piece. After the colors match, the two pieces are twisted into one, and the thickness of the new piece becomes the sum of the thicknesses of the two pieces. We call the rope of length $2$ obtained after shortening the **final rope**. JOI wants to minimize the total cost required to shorten the rope to length $2$. For each color, JOI wants to know the minimum cost required to shorten the rope to length $2$ under the condition that the final rope contains this color. Your task is to help JOI solve this problem.

The first line contains two integers $N, M$, separated by spaces. The second line contains $N$ integers $C_1, C_2, \ldots, C_N$, separated by spaces. The meanings of all numbers are given in the statement.

Output $M$ lines. The $c$-th line $(1\leqslant c\leqslant M)$ contains one integer, representing the minimum cost required to shorten the rope to length $2$ under the condition that the final rope contains color $c$.

#### Sample Explanation 1 With the following steps, you can make the final rope contain color $1$ with total cost $2$. - Dye the $2$-nd piece from the left into color $1$. Fold the rope so that the endpoint that was originally at distance $1$ from the left endpoint becomes the new left endpoint. Now, from left to right, the colors are $1,$ $3,$ $3,$ $2$, and the thicknesses are $2,$ $1,$ $1,$ $1$. - Dye the $4$-th piece from the left into color $1$. Fold the rope so that the endpoint that was originally at distance $2$ from the left endpoint becomes the new left endpoint. Now, from left to right, the colors are $3, 1$, and the thicknesses are $2, 3$. With the following steps, you can make the final rope contain colors $2$ and $3$ with total cost $1$. - Fold the rope so that the endpoint that was originally at distance $3$ from the left endpoint becomes the new left endpoint. Now, from left to right, the colors are $3,$ $2,$ $1$, and the thicknesses are $2,$ $2,$ $1$. - Dye the $3$-rd piece from the left into color $2$. Fold the rope so that the endpoint that was originally at distance $2$ from the left endpoint becomes the new left endpoint. Now, from left to right, the colors are $2, 3$, and the thicknesses are $3, 2$. #### Sample Explanation 2 With the following steps, you can make the final rope contain color $1$ with total cost $2$. - Fold the rope so that the endpoint that was originally at distance $2$ from the left endpoint becomes the new left endpoint. - Dye the $1$-st piece from the left into color $1$. Fold the rope so that the endpoint that was originally at distance $1$ from the left endpoint becomes the new left endpoint. Note that the cost of this dyeing is $2$, because at this time the thickness of the $1$-st piece from the left is $2$. - Fold the rope so that the endpoint that was originally at distance $3$ from the left endpoint becomes the new left endpoint. - Fold the rope so that the endpoint that was originally at distance $1$ from the left endpoint becomes the new left endpoint. #### Constraints and Hints For $15\%$ of the testdata, $N\leqslant 15, M\leqslant 10$. For another $30\%$ of the testdata, $N\leqslant 10^5, M\leqslant 10$. For another $10\%$ of the testdata, $N\leqslant 10^5, M\leqslant 500$. For another $20\%$ of the testdata, $N\leqslant 10^5, M\leqslant 5000$. For all testdata, $2\leqslant N\leqslant 10^6, 1\leqslant M\leqslant N, 1\leqslant C_i\leqslant M(1\leqslant i\leqslant N)$, and in the initial rope, each color $1, 2, \ldots, M$ appears at least once. Translated by ChatGPT 5