Вам дана полоска из клетчатой бумаги из \(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\).
Игра «заливка» играется на этой полоске следующим образом:
- В начале игры вы выбираете один произвольный стартовый квадрат (это не считается за ход).
- Затем, в каждый ход, вы меняете цвет компоненты связности, содержащей стартовый квадрат на любой другой цвет.
Выясните минимальное количество ходов, которое нужно, чтобы перекрасить всю полоску в один цвет.
Примечание
В первом примере одним из оптимальных способов является следующий: нужно выбрать квадрат с номером \(2\) как стартовый, а затем играть следующим образом:
- \([5, 2, 2, 1]\)
- \([5, 5, 5, 1]\)
- \([1, 1, 1, 1]\)
Во втором примере одним из оптимальных способов является следующий: нужно выбрать квадрат с номером \(5\) как стартовый а затем произвести перекраски в цвета \(2, 3, 5, 4\) в таком порядке.
В третьем примере полоска уже состоит только из одного цвета.