AT_joi2017ho_e 縄 (Rope)

[problemUrl]: https://atcoder.jp/contests/joi2017ho/tasks/joi2017ho_e

標準入力から以下の入力を読み込め． - $ 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 $ とするのに必要なコストの最小値を求めるプログラムを作成せよ． - - - - - - ### 制限 すべての入力データは以下の条件を満たす． - $ 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 点\] 追加の制限はない． - - - - - - ### Sample Explanation 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 $ となる． - - - - - - ### Sample Explanation 2 以下のような操作で，色 $ 1 $ を含むようコスト $ 2 $ で長さ $ 2 $ により合わせることができる． - 左から長さ $ 2 $ の位置が端点となるようより合わせる． - 左から $ 1 $ 番目の紐の色を $ 1 $ に塗り替え，左から長さ $ 1 $ の位置が端点となるようより合わせる．塗り替える紐の太さが $ 2 $ なので，コストが $ 2 $ かかることに注意せよ． - 左から長さ $ 3 $ の位置が端点となるようより合わせる． - 左から長さ $ 1 $ の位置が端点となるようより合わせる． - - - - - - ### Sample Explanation 3 $ 1 $ 回のより合わせの前に，複数箇所の紐を塗り替えてもよい．