У Васи есть массив целых чисел, состоящий из n элементов.
Вася производит с массивом следующие операции: каждый раз он находит самый длинный отрезок подряд идущих одинаковых чисел (если таких несколько, то Вася выберет самый левый из них) и удаляет его из массива. Например, если массив Васи имеет вид [13, 13, 7, 7, 7, 2, 2, 2], то после одной операции массив примет вид: [13, 13, 2, 2, 2].
Определите количество описанных операций, которое произведёт Вася до того момента, как его массив станет пустым (то есть Вася удалит из него все элементы).
Выходные данные
Выведите количество операций, которые произведет Вася, чтобы удалить из массива все элементы.
Примечание
В первом примере Вася сначала удалит две пятёрки, стоящие во второй и третьей позициях. После этого массив будет выглядеть как [2, 2]. Во время второй операции Вася удалит две двойки, стоящие в первой и второй позициях. После этого массив станет пустым, и Вася закончит выполнение операций.
Во втором примере Васе нужно пять операций, чтобы удалить все элементы из массива. Во время каждой операции он будет удалять самый левый элемент из массива.
В третьем примере Васе нужно три операции, чтобы удалить все элементы из массива. Во время первой операции он удалит все числа 4, во время второй — все числа 100, а во время третьей — все числа 2.
В четвёртом примере во время первой операции Вася удалит два первых числа 10. После этого массив примет вид [50, 10, 50, 50]. Затем во время второй операции Вася удалит два крайних правых числа 50, массив примет вид [50, 10]. Во время третьей операции — число 50, массив примет вид [10]. Во время последней четвертой операции он удалит единственное число 10. После этого массив Васи станет пустым.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 5 5 2
|
2
|
|
2
|
5
6 3 4 1 5
|
5
|
|
3
|
8
4 4 4 2 2 100 100 100
|
3
|
|
4
|
6
10 10 50 10 50 50
|
4
|