Problem Description

Input Format

Read the following input from standard input:

• The first line contains two integers $N$ and $M$ separated by a space. These represent that there are $N$ ropes in the rope and there are $M$ types of colors.
• The second line contains $N$ integers $C_1, C_2, \ldots, C_N$ separated by spaces. These represent that the color of the $i$-th rope from the left is $C_i$.

Output Format

Output $M$ lines to standard output. The $c$-th ($1 \leq c \leq M$) line should contain the minimum total cost to combine the ropes such that the final rope length is $2$ and includes 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

Task

Given the colors of the ropes that make up the initial rope, create a program that finds the minimum cost for each color to combine the ropes such that the rope includes that color and has a length of $2$.

Constraints

All input data satisfies the following conditions:

• $2 \leq N \leq 1,000,000$.
• $1 \leq M \leq N$.
• $1 \leq C_i \leq M$ ($1 \leq i \leq N$).
• For all integers $c$ satisfying $1 \leq c \leq M$, there exists an $i$ such that $C_i = c$.

Subtasks

Subtask 1 [15 points]

Satisfies the following conditions:

• $N \leq 15$.
• $M \leq 10$.

Subtask 2 [30 points]

Satisfies the following conditions:

• $N \leq 100,000$.
• $M \leq 10$.

Subtask 3 [10 points]

Satisfies the following conditions:

• $N \leq 100,000$.
• $M \leq 500$.

Subtask 4 [25 points]

Satisfies the condition:

• $M \leq 5,000$.

Subtask 5 [20 points]

No additional constraints.

Sample Explanation 1

The following operations can combine the ropes including color $1$ with a cost of $2$ to make the length $2$:
- Repaint the $2$-nd rope from the left to color $1$ and combine it such that the length $1$ from the left is the endpoint. The colors of the ropes from left to right will be $1, 3, 3, 2$ and the thickness will be $2, 1, 1, 1$.
- Repaint the $4$-th rope from the left to color $1$ and combine it such that the length $2$ from the left is the endpoint. The colors of the ropes from left to right will be $3, 1$ and the thickness will be $2, 3$.

Also, the following operations can combine the ropes including colors $2, 3$ with a cost of $1$ to make the length $2$:
- Combine it such that the length $3$ from the left is the endpoint. The colors of the ropes from left to right will be $3, 2, 1$ and the thickness will be $2, 2, 1$.
- Repaint the $3$-rd rope from the left to color $2$ and combine it such that the length $2$ from the left is the endpoint. The colors of the ropes from left to right will be $2, 3$ and the thickness will be $3, 2$.

Sample Explanation 2

The following operations can combine the ropes including color $1$ with a cost of $2$ to make the length $2$:
- Combine it such that the length $2$ from the left is the endpoint.
- Repaint the $1$-st rope from the left to color $1$ and combine it such that the length $1$ from the left is the endpoint. Note that the cost is $2$ because the thickness of the rope to be repainted is $2$.
- Combine it such that the length $3$ from the left is the endpoint.
- Combine it such that the length $1$ from the left is the endpoint.

Sample Explanation 3

Before a single combination, multiple ropes can be repainted.

见题面 Input 部分

见题面 Output 部分