Ms. F wants to take a picture of her kindergarten class. To do this, she has asked all the students to line up side-by-side.
Ms. F wants the picture to look as interesting as possible. She thinks that having two people of the same height stand beside each other is boring, so she wants to remove a number of students from the line so that no two students of the same height are standing beside each other (She will take a picture of the removed students separately).
Since she wants as little commotion as possible, she would like to figure out the minimum number of students that need to be removed from the line so that no two adjacent students have the same height.
The first line of input contains an integer , the number of students in Ms. F’s class. The next line contains integers , the heights of the students in the line.
The minimum number of students that need to be removed from the line so no two adjacent students have the same height.
Sample Input 1
4 1 2 4 2
Sample Output 1
Sample Input 2
10 1 2 3 3 4 3 5 5 5 5
Sample Output 2