| 第16回日本情報オリンピック 予選４ |
|
|
2016年12月11日
情報オリンピック日本委員会
|
ある JOI 関係者は，おもちゃ屋で働いている．今日は，店内にあるぬいぐるみコーナーの整理をすることになった．
ぬいぐるみコーナーの棚には，N 個のぬいぐるみが左から右に一列に並べられている．棚は仕切りにより N 個の区画に区切られており，1 つの区画に 1 個のぬいぐるみを置く．このおもちゃ屋は合計 M 種類のぬいぐるみを売っており，それぞれ 1 から M までの番号が付けられている．棚に並べられた N 個のぬいぐるみは，それぞれこの M 種類のうちのいずれかである．また，それぞれの種類のぬいぐるみは，少なくとも 1 個は存在する．
見栄えを良くするため，同じ種類のぬいぐるみが全て連続して棚に置かれるように，ぬいぐるみを並べ替えたい．次のような方法で，ぬいぐるみを並べ替えることにした．
並べ替えた後，同じ種類のぬいぐるみが全て連続して棚に置かれていなければならない． 並べ替えるために取り出すぬいぐるみの個数の最小値を求めるプログラムを作成せよ．
入力は 1 + N 行からなる．
1 行目には 2 個の整数 N, M (1 ≦ N ≦ 100000, 1 ≦ M ≦ 20) が空白を区切りとして書かれており，ぬいぐるみが N 個あり，種類が M 種類あることを表す．
続く N 行のそれぞれには，1 以上 M 以下の整数が書かれている． N 行のうちの i 行目 (1 ≦ i ≦ N) に書かれた整数は，棚の左から i 番目の区画に置かれたぬいぐるみの種類を表す．各種類について，少なくとも 1 個のぬいぐるみが存在していることが保証される．
並べ替えるために取り出すぬいぐるみの個数の最小値を 1 行で出力せよ．
| 入力例 1 | 入力例 2 |
|---|---|
7 2 1 2 2 2 1 2 1 |
12 4 1 3 2 4 2 1 2 3 1 1 3 4 |
| 出力例 1 | 出力例 2 |
2 |
7 |
入力例 1 においては，最初に置かれているぬいぐるみの種類は左から順に 1， 2， 2， 2， 1， 2， 1 である．並べ替えるために取り出すぬいぐるみの個数を最小にするには，左から 1 番目と 6 番目のぬいぐるみを取り出し，左から 1 番目に種類 2 のぬいぐるみを，左から 6 番目に種類 1 のぬいぐるみを配置すればよい．このとき，取り出すぬいぐるみの個数は 2 個である．
※各入出力例のデータは，右クリック等によりファイルに保存して利用可能です．