Как все вы, наверное, знаете, Добби — это свободный домовой эльф. И как у всех свободных домовых эльфов, у него есть своя одежда. Больше всего на свете Добби любит носить носки. Причем они обязательно должны быть разными, иначе жизнь будет слишком скучной.
Чтобы часто не ходить в магазин, Добби купил сразу очень много носков двух разных цветов и выложил их в один ряд на полке. Каждое утро он подходит к ней и берет два соседних носка (разумеется, разноцветных). После этого весь ряд сдвигается так, что пустот в нем не остается.
Вы случайно заметили, в каком порядке разложил свои носки Добби. И вам стало любопытно, на сколько дней их хватит. Не забывайте, что Добби — умный домовой эльф, а значит, будет действовать так, чтобы носков хватило на как можно больший период.
В первой строке входных данных дано натуральное число 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) и больше нет соседних носков одного цвета. Можно заметить, что такая последовательность действий является оптимальной.
Во втором же тесте все носки изначально одного цвета, а значит, Добби не может выбрать себе ни одной пары.
Горацио и Пьер играют в односторонний «Морской бой» — модификацию обычной игры «Морской бой». Сначала Пьер расставляет на поле 10 × 10 клеток стандартный набор кораблей: 4 однопалубных, 3 двухпалубных, 2 трехпалубных и 1 четырёхпалубный (если в корабле i палуб, то он занимает i подряд идущих клеток по вертикали или горизонтали).
По правилам игры корабли не могут пересекаться, а также вплотную прилегать друг к другу (между кораблями должна быть хотя бы одна клетка).
Затем Горацио делает n выстрелов в различные клетки поля (расположение кораблей ему неизвестно). Корабль считается потопленным, если в каждую его клетку попал выстрел.
Напишите программу, которая определит, какое минимальное и максимальное количество кораблей мог потопить Горацио.
На вход дается единственное целое число — количество выстрелов n (0 ≤ n ≤ 100).
Выведите два числа через пробел — минимальное и максимальное количество потопленных кораблей.
7
0 5
В примере из условия Горацио делает 7 выстрелов. В худшем для него случае он все разы промахнется, а в лучшем потопит 5 кораблей, например, 4 однопалубных и один двухпалубный.