005 - 縄 (Rope)

問題

赤ちゃんの JOI くんは縄で遊んでいる．縄の長さは N であり，左右にまっすぐ伸びている．縄は太さ 1，長さ 1 の紐 (ひも) が N 個つながってできている．縄には M 種類の色が使われており，左から i 番目の紐の色は C_i (1 ≤ C_i ≤ M) である．

JOI くんは縄をより合わせて短くしていく．具体的には，以下の操作を縄の長さが 2 となるまで繰り返す．

• 縄の長さを L とする．ある整数 j (1 ≤ j < L) を取り，左から長さ j の位置が新たに左の端点となるよう，縄をより合わせていく．すなわち，
• j ≤ L/2 のとき，各 i (1 ≤ i ≤ j) について，左から i 番目の紐と，左から 2j − i + 1 番目の紐をより合わせる．このとき元々右の端点だった位置は引き続き右の端点となり，縄の長さは L − j となる．
• j > L/2 のとき，各 i (2j − L + 1 ≤ i ≤ j) について，左から i 番目の紐と，左から 2j − i + 1 番目の紐をより合わせる．このとき元々左の端点だった位置は右の端点となり，縄の長さは j となる．
• このとき，より合わされる各紐の組について，色を揃えなければならない．紐はより合わせる直前に，任意の色に塗り替えることができるが，塗り替えた場合その太さと同じだけのコストがかかる．色を揃えたのち，紐はより合わされ，できた紐の太さはより合わされた 2 つの紐の太さの和となる．

JOI くんは，縄の長さが 2 となるまでに行う操作のコストの総和を最小化したいと思っている．JOI くんはすべての色について，最終的な縄がその色を含むように操作を行った場合のコストの総和の最小値を求めたいと思っている．

あなたの仕事は JOI くんに代わってこの問題を解くことである．

課題

はじめの縄を構成する紐の色が与えられたとき，それぞれの色について，縄がその色を含み，かつ長さ を 2 とするのに必要なコストの最小値を求めるプログラムを作成せよ．

入力

標準入力から以下の入力を読み込め．

• 1 行目には 2 個の整数 N, M が空白を区切りとして書かれている．これらは縄を構成する紐が N 個あり，それらの色が M 種類あることを表す．
• 2 行目には N 個の整数 C₁, C₂, ..., C_N が空白を区切りとして書かれている．これらは左から i 番目の紐の色が C_i であることを表す．

出力

標準出力に M 行で出力せよ．M 行のうちの c (1 ≤ c ≤ M) 行目には，最終的な縄の長さが 2 となり，その縄に色 c を含むようにより合わせるためのコストの総和の最小値を 1 行で出力せよ．

制限

すべての入力データは以下の条件を満たす．

• 2 ≤ N ≤ 1 000 000．
• 1 ≤ M ≤ N．
• 1 ≤ C_i ≤ M (1 ≤ i ≤ N)．
• 1 ≤ c ≤ M を満たすすべての整数 c について，C_i = c となる i が存在する.

小課題

小課題 1 [15 点]

以下の条件を満たす．

• N ≤ 15．
• M ≤ 10．

小課題 2 [30 点]

以下の条件を満たす．

• N ≤ 100 000．
• M ≤ 10．

小課題 3 [10 点]

以下の条件を満たす．

• N ≤ 100 000．
• M ≤ 500．

小課題 4 [25 点]

• M ≤ 5 000 を満たす．

小課題 5 [20 点]

追加の制限はない．

入出力例

入力例 1

5 3
1 2 3 3 2

出力例 1

2
1
1

以下のような操作で，色 1 を含むようコスト 2 で長さ 2 により合わせることができる．

• 左から 2 番目の紐を色 1 に塗り替え，左から長さ 1 の位置が端点となるようより合わせる．左から順に縄の色は 1, 3, 3, 2 となり，太さは 2, 1, 1, 1 となる．
• 左から 4 番目の紐の色を 1 に塗り替え，左から長さ 2 の位置が端点となるようより合わせる．左から順に縄の色は 3, 1 となり，太さは 2, 3 となる．

また，以下のような操作で，色 2, 3 を含むようコスト 1 で長さ 2 により合わせることができる．

• 左から長さ 3 の位置が端点となるようより合わせる．左から順に縄の色は 3, 2, 1 となり，太さは 2, 2, 1 となる．
• 左から 3 番目の紐の色を 2 に塗り替え，左から長さ 2 の位置が端点となるようより合わせる．左から順に縄の色は 2, 3 となり，太さは 3, 2 となる．

入力例 2

7 3
1 2 2 1 3 3 3

出力例 2

2
2
2

以下のような操作で，色 1 を含むようコスト 2 で長さ 2 により合わせることができる．

• 左から長さ 2 の位置が端点となるようより合わせる．
• 左から 1 番目の紐の色を 1 に塗り替え，左から長さ 1 の位置が端点となるようより合わせる．塗り替える紐の太さが 2 なので，コストが 2 かかることに注意せよ．
• 左から長さ 3 の位置が端点となるようより合わせる．
• 左から長さ 1 の位置が端点となるようより合わせる．

入力例 3

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

出力例 3

3
3
4

1 回のより合わせの前に，複数箇所の紐を塗り替えてもよい．