Problem Description

This problem is translated from JOI 2017 Final T5「縄 / Rope」

JOI Baby is playing with a rope. The rope can be considered as a horizontal line segment of length $N$. The rope is made up of $N$ segments, each of length $1$ and thickness $1$. There are $M$ different colors for the segments, and the color of the $i$-th segment from the left $(1 \leqslant i \leqslant N)$ is $C_i (1 \leqslant C_i \leqslant M)$. The left endpoint of the rope is the left endpoint of the first segment from the left, and the right endpoint of the rope is the right endpoint of the first segment from the right. Clearly, the right endpoint of the $i$-th segment from the left $(1 \leqslant i \leqslant N)$ is at a distance of $i$ from the left endpoint of the rope.

JOI shortens the length of the rope. Specifically, JOI repeatedly performs the following process until the length of the rope is reduced to $2$.

• Suppose the current length of the rope is $L$. Choose an integer $j (1 \leqslant j < L)$ such that the $j$-th segment from the left becomes the new left endpoint of the rope, and fold the rope. That is,
• If $j \leqslant \frac{L}{2}$, then twist the $i$-th segment from the left $(1 \leqslant i \leqslant j)$ with the $(2j-i+1)$-th segment from the left. In this case, the original right endpoint of the rope remains the right endpoint, and the new length of the rope becomes $L-j$.
• If $j > \frac{L}{2}$, then twist the $i$-th segment from the left $(2j-L+1 \leqslant i \leqslant j)$ with the $(2j-i+1)$-th segment from the left. In this case, the original left endpoint of the rope becomes the new right endpoint, and the new length of the rope becomes $j$.
• Two segments can only be twisted together if they have the same color. Before twisting, the color of a segment can be changed to any other color. The cost of changing the color of a segment is equal to its thickness. After twisting, the new segment formed will have a thickness equal to the sum of the thicknesses of the two original segments.

The rope with a length of $2$ is called the final rope. JOI wants to minimize the cost required to shorten the rope to a length of $2$. For each color, JOI wants to know the minimum cost required to shorten the rope to a length of $2$ while ensuring that the final rope contains that color.

Your task is to help JOI solve this problem.

Input Format

The first line contains two integers $N$ and $M$, separated by a space.
The second line contains $N$ integers $C_1, C_2, \ldots, C_N$, separated by spaces.
The meanings of these numbers are as described in the problem statement.

Output Format

There are $M$ lines in total. The $c$-th line $(1 \leqslant c \leqslant M)$ contains an integer, which represents the minimum cost required to shorten the rope to a length of $2$ while ensuring that the final rope contains color $c$.

Sample Input and Output

Sample Input #1

5 3
1 2 3 3 2

Sample Output #1

2
1
1

Sample Input #2

7 3
1 2 2 1 3 3 3

Sample Output #2

2
2
2

Sample Input #3

10 3
2 2 1 1 3 3 2 1 1 2

Sample Output #3

3
3
4

Notes/Hints

Sample Explanation 1

By following these steps, it is possible to include color $1$ in the final rope with a cost of $2$:
- Color the second segment from the left to color $1$. Fold the rope so that the endpoint originally at a distance of $1$ from the left becomes the new left endpoint. Now, the colors of the segments from left to right are $1, 3, 3, 2$, and their thicknesses are $2, 1, 1, 1$.
- Color the fourth segment from the left to color $1$. Fold the rope so that the endpoint originally at a distance of $2$ from the left becomes the new left endpoint. Now, the colors of the segments from left to right are $3, 1$, and their thicknesses are $2, 3$.

By following these steps, it is possible to include color $2$ and $3$ in the final rope with a cost of $1$:
- Fold the rope so that the endpoint originally at a distance of $3$ from the left becomes the new left endpoint. Now, the colors of the segments from left to right are $3, 2, 1$, and their thicknesses are $2, 2, 1$.
- Color the third segment from the left to color $2$. Fold the rope so that the endpoint originally at a distance of $2$ from the left becomes the new left endpoint. Now, the colors of the segments from left to right are $2, 3$, and their thicknesses are $3, 2$.

Sample Explanation 2

By following these steps, it is possible to include color $1$ in the final rope with a cost of $2$:
- Fold the rope so that the endpoint originally at a distance of $2$ from the left becomes the new left endpoint.
- Color the first segment from the left to color $1$. Fold the rope so that the endpoint originally at a distance of $1$ from the left becomes the new left endpoint. Note that the cost of this coloring is $2$ because the thickness of the first segment is $2$.
- Fold the rope so that the endpoint originally at a distance of $3$ from the left becomes the new left endpoint.
- Fold the rope so that the endpoint originally at a distance of $1$ from the left becomes the new left endpoint.

Data Range and Hints

For $15\%$ of the data, $N \leqslant 15, M \leqslant 10$.
For another $30\%$ of the data, $N \leqslant 10^5, M \leqslant 10$.
For another $10\%$ of the data, $N \leqslant 10^5, M \leqslant 500$.
For another $20\%$ of the data, $N \leqslant 10^5, M \leqslant 5000$.
For all data, $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 state of the rope, each color from $1$ to $M$ appears at least once.

见题面 Input 部分

见题面 Output 部分