У вас есть изображение размером \(1\) на \(n\) пикселей. \(i\)-й пиксель изображения имеет цвет \(a_i\). Для каждого цвета число пикселей, имеющих этот цвет, не более \(20\).
Вы можете выполнять следующую операцию, которая обычно называется «заливка» в редакторах изображений:
- выбрать цвет — целое число от \(1\) до \(n\);
- выбрать некоторый пиксель изображения;
- изменить цвет всех связных с выбранным пикселем на выбранный цвет (два пикселя одного цвета называются связными, если все пиксели между ними имеют такой же цвет, как и эти два пикселя).
Вычислите минимальное количество операций, необходимое, чтобы все пиксели изображения стали одного цвета.
Выходные данные
Для каждого набора входных данных выведите одно целое число: минимальное количество операций, необходимое, чтобы сделать все пиксели изображения одного цвета.
Примечание
В первом примере оптимальное решение — применить операцию на третьем пикселе, изменив его цвет на \(2\), и затем применить операцию на любом пикселе цвета \(2\), изменив его и всех связных пикселей цвет на \(1\). Последовательность операций тогда будет: \([1, 2, 3, 2, 1] \to [1, 2, 2, 2, 1] \to [1, 1, 1, 1, 1]\).
Во втором примере мы можем либо изменить все \(1\) на \(2\) за одну операцию, или все \(2\) на \(1\) также за одну операцию.
В третьем примере один из возможных способов сделать все пиксели одного цвета — применить операцию на первом, третьем и четвертом пикселе, каждый раз выбирая цвет \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5
1 2 3 2 1
4
1 1 2 2
5
1 2 1 4 2
|
2
1
3
|