D. Игра-заливка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана полоска из клетчатой бумаги из $$$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 \le n \le 5000$$$) — количество квадратов.

Вторая строка содержит целые числа $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 5000$$$) — изначальные цвета квадратов.

Выходные данные

Выведите одно целое число — минимальное количество ходов, которое нужно сделать.

Примеры
Входные данные
4
5 2 2 1
Выходные данные
2
Входные данные
8
4 5 2 2 1 3 5 5
Выходные данные
4
Входные данные
1
4
Выходные данные
0
Примечание

В первом примере одним из оптимальных способов является следующий: нужно выбрать квадрат с номером $$$2$$$ как стартовый, а затем играть следующим образом:

  • $$$[5, 2, 2, 1]$$$
  • $$$[5, 5, 5, 1]$$$
  • $$$[1, 1, 1, 1]$$$

Во втором примере одним из оптимальных способов является следующий: нужно выбрать квадрат с номером $$$5$$$ как стартовый а затем произвести перекраски в цвета $$$2, 3, 5, 4$$$ в таком порядке.

В третьем примере полоска уже состоит только из одного цвета.