줄

JOI는 줄을 가지고 노는 아기다. 길이가 $N$인 줄이 왼쪽에서 오른쪽으로 곧게 놓여 있다. 줄은 $N$개의 끈이 일직선으로 이어진 것이고, 각 끈의 길이와 굵기는 모두 1이다. 줄에 쓰인 색은 모두 $M$가지이며, 왼쪽에서 $i$번째 끈의 색은 $C_i$ ($1 \le C_i \le M$)이다.

JOI는 줄의 길이가 2가 될 때까지 다음 과정을 반복해서 줄을 줄인다.

• 현재 줄의 길이를 $L$이라 하자. 정수 $j$ ($1 \le j < L$)를 하나 고른다. 줄의 왼쪽 끝에서 길이 $j$만큼 떨어진 지점이 새로운 왼쪽 끝이 되도록 줄을 접어 끈을 합친다. 정확히는 다음과 같다.
  • $j \le L/2$이면 각 $i$ ($1 \le i \le j$)에 대해 왼쪽에서 $i$번째 끈을 왼쪽에서 $(2j - i + 1)$번째 끈과 합친다. 원래 줄의 오른쪽 끝은 그대로 오른쪽 끝이 되고, 줄의 길이는 $L - j$가 된다.
  • $j > L/2$이면 각 $i$ ($2j - L + 1 \le i \le j$)에 대해 왼쪽에서 $i$번째 끈을 왼쪽에서 $(2j - i + 1)$번째 끈과 합친다. 원래 줄의 왼쪽 끝이 오른쪽 끝이 되고, 줄의 길이는 $j$가 된다.
• 두 끈을 합치려면 두 끈의 색이 같아야 한다. 끈을 다른 끈과 합치기 전에 그 끈의 색을 바꿀 수 있다. 끈 하나의 색을 바꾸는 비용은 그 끈의 굵기와 같다. 색을 맞춘 두 끈은 끈 하나로 합쳐지고, 합쳐진 끈의 굵기는 두 끈의 굵기의 합이다.

JOI는 줄의 길이가 2가 될 때까지 드는 비용의 총합을 최소로 하려고 한다. 각 색마다, 길이가 2인 최종 줄에 그 색의 끈이 포함되도록 줄을 줄일 때 드는 최소 총비용을 구하고 싶다.

처음 줄의 끈 색이 주어질 때, 각 색에 대해 최종 길이 2의 줄에 그 색의 끈이 포함되도록 하는 최소 총비용을 구하는 프로그램을 작성하시오.

첫째 줄에 두 정수 $N$, $M$이 공백으로 구분되어 주어진다. 줄이 $N$개의 끈으로 이루어져 있고 끈에 쓰인 색이 $M$가지라는 뜻이다.

둘째 줄에 $N$개의 정수 $C_1, C_2, \ldots, C_N$이 공백으로 구분되어 주어진다. 왼쪽에서 $i$번째 끈의 색이 $C_i$ ($1 \le C_i \le M$)라는 뜻이다.

$M$개의 줄을 출력한다. $c$번째 줄 ($1 \le c \le M$)에는 길이가 2인 최종 줄에 색 $c$인 끈이 포함되도록 줄을 줄일 때 드는 최소 총비용을 출력한다.

• $2 \le N \le 1\,000\,000$
• $1 \le M \le N$
• $1 \le C_i \le M$ ($1 \le i \le N$)
• $1 \le c \le M$인 모든 $c$에 대해 $C_i = c$인 정수 $i$가 존재한다.