atcoder#AGC026A. [AGC026A] Colorful Slimes 2

[AGC026A] Colorful Slimes 2

配点 : 200200

問題文

高橋君は異世界に住んでいます。この世界のスライムの色は 1000010000 色存在し,色 1,2,...,100001, 2, ..., 10000 と呼ぶことにします。

高橋君は NN 匹のスライムを飼っており,スライムは左右に一列に並んでいます。左から ii 匹目のスライムの色は aia_i です。 もし同じ色どうしのスライムが隣り合っていると,そのスライムたちは合体してしまいます。高橋君は小さいスライムのほうが好きなので,魔法でスライムの色を何匹か変えることにしました。

高橋君は魔法を唱えることで,どれか 11 匹のスライムの色を,1000010000 色のうち好きな色に変えることが出来ます。 どのスライムたちも合体しないようにするには,最小で何回魔法を唱える必要があるでしょうか?

制約

  • 2N1002 \leq N \leq 100
  • 1aiN1 \leq a_i \leq N
  • 入力される値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

NN

a1a_1 a2a_2 ...... aNa_N

出力

高橋君が唱える必要のある魔法の最小回数を出力して下さい。

5
1 1 2 2 2
2

例えば左から 22 匹目のスライムの色を44,左から 44 匹目のスライムの色を 55 に変えると, スライムの色は 1,4,2,5,21, 4, 2, 5, 2 となり,これで条件を満たします。

3
1 2 1
0

11 匹目と 33 匹目のスライムは同じ色ですが隣り合っていないため,魔法を唱える必要はありません。

5
1 1 1 1 1
2

たとえば 2,42, 4 匹目のスライムの色を 22 に変えると,スライムの色は 1,2,1,2,11, 2, 1, 2, 1 となり,これで条件を満たします。

14
1 2 2 3 3 3 4 4 4 4 1 2 3 4
4