Фермер Джон фотографирует N своих коров (2≤N≤1000).
Каждая корова имеет целое число - "ID породы" в интервале 1…100. ФД разбить всех коров на несвязные группы (другими словами, поместить каждую корову ровно в одну группу) и затем выставить группы так, чтобы сумма "ID породы" коров в первой группе была чётной, во второй - нечётной и т.д., чередуя чётные и нечётные.
Какое максимальное количество групп может сформировать ФД?
Входные данные
Первая строка ввода содержит число N. Следующая строка содержит N разделённых пробелом целых чисел, представляющих "ID породы".
Выходные данные
Максимально возможное количество групп на фото ФД. Можно доказать, что хотя бы одна группа будет всегда.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснения |
| 1 |
7
1 3 5 7 9 11 13
|
3 |
В этом примере один из способов сформировать максимальное количество (3) групп так:
1 группа: 1 3
2 группа: 5 7 9
3 группа: 11 13 |
| 2 |
7
11 2 17 13 1 15 3
|
5 |
В этом примере один из способов сформировать максимальное число (5) групп так: 1 группа: 2
2 группа: 11
3 группа: 13 1
4 группа: 15
5 группа: 17 3. |