A - Colorful Slimes 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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

出力

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


入力例 1Copy

Copy
5
1 1 2 2 2

出力例 1Copy

Copy
2

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


入力例 2Copy

Copy
3
1 2 1

出力例 2Copy

Copy
0

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


入力例 3Copy

Copy
5
1 1 1 1 1

出力例 3Copy

Copy
2

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


入力例 4Copy

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

出力例 4Copy

Copy
4

Score : 200200 points

Problem Statement

Takahashi lives in another world. There are slimes (creatures) of 1000010000 colors in this world. Let us call these colors Color 1,2,...,100001, 2, ..., 10000.

Takahashi has NN slimes, and they are standing in a row from left to right. The color of the ii-th slime from the left is aia_i. If two slimes of the same color are adjacent, they will start to combine themselves. Because Takahashi likes smaller slimes, he has decided to change the colors of some of the slimes with his magic.

Takahashi can change the color of one slime to any of the 1000010000 colors by one spell. How many spells are required so that no slimes will start to combine themselves?

Constraints

  • 2N1002 \leq N \leq 100
  • 1aiN1 \leq a_i \leq N
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

NN
a1a_1 a2a_2 ...... aNa_N

Output

Print the minimum number of spells required.


Sample Input 1Copy

Copy
5
1 1 2 2 2

Sample Output 1Copy

Copy
2

For example, if we change the color of the second slime from the left to 44, and the color of the fourth slime to 55, the colors of the slimes will be 1,4,2,5,21, 4, 2, 5, 2, which satisfy the condition.


Sample Input 2Copy

Copy
3
1 2 1

Sample Output 2Copy

Copy
0

Although the colors of the first and third slimes are the same, they are not adjacent, so no spell is required.


Sample Input 3Copy

Copy
5
1 1 1 1 1

Sample Output 3Copy

Copy
2

For example, if we change the colors of the second and fourth slimes from the left to 22, the colors of the slimes will be 1,2,1,2,11, 2, 1, 2, 1, which satisfy the condition.


Sample Input 4Copy

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

Sample Output 4Copy

Copy
4


2025-01-05 (Sun)
00:01:13 +00:00