Единственное различие между двумя версиями задачи заключается в том, что в этой версии вам нужно найти максимальный возможный ответ.

Гомеру очень нравятся массивы. Сегодня он красит массив $$$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)})$$$, максимально. Найдите, чему равно это значение.