Даша очень любит морских свинок. В связи с этим, она решила поселить как можно больше морских свинок у себя дома и разработала план на ближайшие \(n\) дней. Каждый день она будет либо покупать новую морскую свинку, либо вызывать врача, чтобы он осмотрел всех ее питомцев.
К сожалению, магазин, в котором она собралась покупать морских свинок, не разбирается в них. Поэтому не может определить их пол. Даша тоже не может этого сделать. Единственный, кто может помочь — врач.
Для содержания морских свинок нужны вольеры. Покупать их Даша планирует в том же магазине. К сожалению, там продается только один вид — двухместный вольер. В нем может жить не более двух морских свинок.
Так как Даша не хочет нанести моральную травму своим питомцам — она не будет селить двух морских свинок разного пола в один вольер.
Помогите Даше посчитать, сколько минимум вольеров нужно купить, чтобы ни в один момент времени две морские свинки разных полов не жили в одном вольере.
В рамках этой задачи мы считаем, что у морских свинок всего два пола — мужской и женский.
Выходные данные
Для каждого набора входных данных выведите одно число — сколько минимум вольеров нужно купить Даше, чтобы ни в один момент времени две морские свиньи разного пола не жили вместе.
Примечание
В первом наборе входных данных Даше нужно селить каждую морскую свинку в отдельный вольер, так как она не знает их пол.
Во втором наборе входных данных Даша купит \(0\) морских свинок, а значит ей потребуется \(0\) вольеров.
В третьем наборе входных данных Даше нужно \(3\) вольера, чтобы поселить каждую морскую свинку в отдельный вольер до прихода врача на \(4\)-й день. Когда она узнает их пол, то хотя бы две морские свинки окажутся одного пола и их можно будет поселить в один вольер, а третью - в другой вольер. Таким образом у нее будет один свободный вольер, в который она может поселить новую морскую свинку. Таким образом ответ \(3\).
В четвертом наборе входных данных покажем, что \(4\) - оптимальный ответ.
Для начала заметим, что первые четыре морские свинки можно поселить по одной в вольер. Затем придет врач и определит их пол. Среди этих четырех морских свинок будет хотя бы одна пара одного пола, потому что: либо морских свинок мужского пола хотя бы \(2\), либо их не больше \(1\), а значит женского пола хотя бы \(3\). Теперь мы можем поселить эту пару в один вольер, а две остальные - в отдельные. У нас останется еще один пустой вольер куда можно поселить новую свинку.
Теперь покажем, что ответ не меньше \(4\). Пусть среди первых \(4\) морских свинок \(3\) имеют женский пол и \(1\) - мужской. Нам нужно минимум \(3\) вольера чтобы их расселить. Тогда, когда мы купим новую морскую свинку - нам понадобится еще один вольер, в которые мы ее поселим, так как мы не знаем ее пол.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3
1 1 1
3
2 2 2
5
1 1 1 2 1
10
1 2 1 2 1 2 1 2 1 2
20
1 2 1 1 1 1 1 2 1 2 1 2 2 1 1 1 1 1 1 1
20
2 1 1 2 1 1 2 1 2 2 1 1 1 2 2 1 1 1 1 2
|
3
0
3
4
12
9
|