B1. Покраска массива I
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

Первая строка содержит целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$).

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

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

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

В первом примере можно выбрать $$$a^{(0)} = [1,2,3,3]$$$, $$$a^{(1)} = [1,2,3]$$$ и $$$\mathit{seg}(a^{(0)}) = \mathit{seg}(a^{(1)}) = 3$$$. Таким образом, ответ $$$3+3 = 6$$$.

Во втором примере можно выбрать $$$a^{(0)} = [1,2,3,4,5,6,7]$$$ и $$$a^{(1)}$$$ пустое. Мы видим, что $$$\mathit{seg}(a^{(0)}) = 7$$$ и $$$\mathit{seg}(a^{(1)}) = 0$$$. Таким образом, ответ $$$7+0 = 7$$$.