eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Еще больше странных фотографий

Еще больше странных фотографий

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Фермер Джон фотографирует n своих коров.

Каждая корова имеет целое число - "ID породы" в интервале 1..100. ФД хочет разбить всех коров на несвязные группы (другими словами, поместить каждую корову ровно в одну группу) и затем выставить группы так, чтобы сумма "ID породы" коров в первой группе была чётной, во второй - нечётной и т.д., чередуя чётные и нечётные.

Какое максимальное количество групп может сформировать ФД?

Входные данные

Первая строка содержит число n (2n1000). Следующая строка содержит n целых чисел, представляющих "ID породы".

Выходные данные

Выведите максимально возможное количество групп на фото ФД. Можно доказать, что хотя бы одна группа будет всегда.

Пример 1

В этом примере один из способов сформировать максимальное количество (3) групп так:

1 группа: 1 3
2 группа: 5 7 9
3 группа: 11 13

Пример 2

В этом примере один из способов сформировать максимальное число (5) групп так: 1 группа: 2.

2 группа: 11
3 группа: 13 1
4 группа: 15
5 группа: 17 3

Пример

Входные данные #1
7
1 3 5 7 9 11 13
Выходные данные #1
3
Входные данные #2
7
11 2 17 13 1 15 3
Выходные данные #2
5
Источник 2021 USACO Январь, Бронза