E. Удаление отрезков
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Васи есть массив целых чисел, состоящий из n элементов.

Вася производит с массивом следующие операции: каждый раз он находит самый длинный отрезок подряд идущих одинаковых чисел (если таких несколько, то Вася выберет самый левый из них) и удаляет его из массива. Например, если массив Васи имеет вид [13, 13, 7, 7, 7, 2, 2, 2], то после одной операции массив примет вид: [13, 13, 2, 2, 2].

Определите количество описанных операций, которое произведёт Вася до того момента, как его массив станет пустым (то есть Вася удалит из него все элементы).

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

В первой строке следует целое число n (1 ≤ n ≤ 200 000) — количество элементов в массиве.

Во второй строке следует последовательность a1, a2, ..., an (1 ≤ ai ≤ 109) — описание массива Васи.

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

Выведите количество операций, которые произведет Вася, чтобы удалить из массива все элементы.

Примеры
Входные данные
4
2 5 5 2
Выходные данные
2
Входные данные
5
6 3 4 1 5
Выходные данные
5
Входные данные
8
4 4 4 2 2 100 100 100
Выходные данные
3
Входные данные
6
10 10 50 10 50 50
Выходные данные
4
Примечание

В первом примере Вася сначала удалит две пятёрки, стоящие во второй и третьей позициях. После этого массив будет выглядеть как [2, 2]. Во время второй операции Вася удалит две двойки, стоящие в первой и второй позициях. После этого массив станет пустым, и Вася закончит выполнение операций.

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

В третьем примере Васе нужно три операции, чтобы удалить все элементы из массива. Во время первой операции он удалит все числа 4, во время второй — все числа 100, а во время третьей — все числа 2.

В четвёртом примере во время первой операции Вася удалит два первых числа 10. После этого массив примет вид [50, 10, 50, 50]. Затем во время второй операции Вася удалит два крайних правых числа 50, массив примет вид [50, 10]. Во время третьей операции — число 50, массив примет вид [10]. Во время последней четвертой операции он удалит единственное число 10. После этого массив Васи станет пустым.