Единственное различие между двумя версиями задачи заключается в том, что в этой версии вам нужно найти минимальный возможный ответ.
Гомеру очень нравятся массивы. Сегодня он красит массив \(a_1, a_2, \dots, a_n\) двумя видами цветов, белым и черным. Покраска массива \(a_1, a_2, \dots, a_n\) описывается массивом \(b_1, b_2, \dots, b_n\), где \(b_i\) обозначает цвет \(a_i\) (\(0\) для белого и \(1\) для черного).
Согласно покраске \(b_1, b_2, \dots, b_n\) массив \(a\) разделяется на два новых массива \(a^{(0)}\) и \(a^{(1)}\), где \(a^{(0)}\) — это подпоследовательность всех белых элементов в \(a\), а \(a^{(1)}\) — это подпоследовательность всех черных элементов в \(a\). Например, если \(a = [1,2,3,4,5,6]\) и \(b = [0,1,0,1,0,0]\), то \(a^{(0)} = [1,3,5,6]\) и \(a^{(1)} = [2,4]\).
Количество отрезков в массиве \(c_1, c_2, \dots, c_k\), обозначаемое \(\mathit{seg}(c)\), — это количество элементов, которое останется, если объединить все соседние элементы с одинаковым значением в \(c\). Например, количество отрезков в \([1,1,2,2,3,3,3,2]\) равно \(4\), так как массив станет равным \([1,2,3,2]\) после объединения соседних элементов с одинаковым значением. В частности, количество отрезков в пустом массиве равно \(0\).
Гомер хочет найти покраску \(b\), согласно которой суммарное количество отрезков в \(a^{(0)}\) и \(a^{(1)}\), т. е. \(\mathit{seg}(a^{(0)})+\mathit{seg}(a^{(1)})\), минимально. Найдите, чему равно это значение.
Примечание
В первом примере можно выбрать \(a^{(0)} = [1,1,2,2]\), \(a^{(1)} = [2,3]\) и \(\mathit{seg}(a^{(0)}) = \mathit{seg}(a^{(1)}) = 2\). Таким образом, ответ \(2+2 = 4\).
Во втором примере можно выбрать \(a^{(0)} = [1,1,1,1]\), \(a^{(1)} = [2,2,2]\) и \(\mathit{seg}(a^{(0)}) = \mathit{seg}(a^{(1)}) = 1\). Таким образом, ответ \(1+1 = 2\).