Вам дана полоска из клетчатой бумаги из n раскрашенных квадратов, пронумерованных от 1 до n слева направо. Квадрат под номером i изначально покрашен в цвет c
i.
Скажем, что квадраты i и j лежат в одной компоненте, если c
i = c
j и c
i = c
k для всех k, удовлетворяющих i < k < j. Иначе говоря, все квадраты на отрезке от i до j должны иметь одинаковый цвет.
Например, у полоски [3,3,3] есть 1 компонента связности, а у [5,2,4,4] их 3.
Игра «заливка» играется на этой полоске следующим образом:
В начале игры вы выбираете один произвольный стартовый квадрат (это не считается за ход).
Затем, в каждый ход, вы меняете цвет компоненты связности, содержащей стартовый квадрат на любой другой цвет.
Выясните минимальное количество ходов, которое нужно, чтобы перекрасить всю полоску в один цвет.
Входные данные:
Первая строка содержит одно целое число n (1 ≤ n ≤ 5000) — количество квадратов.
Вторая строка содержит целые числа c
1,c
2,…,c
n (1 ≤ c
i ≤ 5000) — изначальные цвета квадратов.
Выходные данные:
Выведите одно целое число — минимальное количество ходов, которое нужно сделать.
Примеры:
| Входные данные |
Выходные данные |
4
5 2 2 1 |
2 |
8
4 5 2 2 1 3 5 5 |
4 |
1
4 |
0 |
Пояснение:
Один из оптимальных способов в первом примере: [5, 2, 2, 1] -> [5, 2, 2, 2] -> [5, 5, 5, 5]