縄 (Rope)

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

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

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

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

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

課題

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

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

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

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

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

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

小課題 1 [15 点]

以下の条件を満たす．

• \(N \leqq 15\)．
• \(M \leqq 10\)．

小課題 2 [30 点]

以下の条件を満たす．

• \(N \leqq 100\,000\)．
• \(M \leqq 10\)．

小課題 3 [10 点]

以下の条件を満たす．

• \(N \leqq 100\,000\)．
• \(M \leqq 500\)．

小課題 4 [25 点]

• \(M \leqq 5\,000\) を満たす．

小課題 5 [20 点]

追加の制限はない．

JOI 2017 · JCIOI · CC BY-SA 4.0