Как все вы, наверное, знаете, Добби — это свободный домовой эльф. И как у всех свободных домовых эльфов, у него есть своя одежда. Больше всего на свете Добби любит носить носки. Причем они обязательно должны быть разными, иначе жизнь будет слишком скучной.
Чтобы часто не ходить в магазин, Добби купил сразу очень много носков двух разных цветов и выложил их в один ряд на полке. Каждое утро он подходит к ней и берет два соседних носка (разумеется, разноцветных). После этого весь ряд сдвигается так, что пустот в нем не остается.
Вы случайно заметили, в каком порядке разложил свои носки Добби. И вам стало любопытно, на сколько дней их хватит. Не забывайте, что Добби — умный домовой эльф, а значит, будет действовать так, чтобы носков хватило на как можно больший период.
В первой строке входных данных дано натуральное число n (1 ≤ n ≤ 106) — количество носков у Добби.
Во второй строке содержится последовательность из n чисел: нулей и единиц. Каждое число обозначает цвет соответствующего носка в ряду.
Выведите одно число — максимальное количество дней, в течение которых Добби сможет носить свои носки.
6
1 1 1 0 0 1
2
4
1 1 1 1
0
В первом тесте для Добби оптимально взять третий и четвертый носки. После этого ряд превратится в (1, 1, 0, 1). Затем он снова берет третий и четвертый. Остается (1, 1) и больше нет соседних носков одного цвета. Можно заметить, что такая последовательность действий является оптимальной.
Во втором же тесте все носки изначально одного цвета, а значит, Добби не может выбрать себе ни одной пары.
