Ще більше дивних фотографій#11196

Ще більше дивних фотографій

1 секунда

128 мегабайтів

Середня

Фермер Джон фотографує $n$ своїх корів.

Кожна корова має ціле число - "ID породи" в діапазоні $1 \dots 100$ . Фермер Джон хоче розподілити всіх корів на неперетинні групи (тобто, кожна корова повинна бути в одній і лише одній групі) і розташувати ці групи так, щоб сума "ID породи" корів у першій групі була парною, у другій - непарною, і так далі, чергуючи парні та непарні суми.

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

Вхідні дані

Перший рядок містить число $n$ ( $2 \leq n \leq 1000$ 2 \le n \le 1000). Другий рядок містить $n$ цілих чисел, що представляють "ID породи".

Вихідні дані

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

Приклади

У цьому прикладі один зі способів сформувати максимальну кількість ( $3$ ) груп такий:

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

У цьому прикладі один зі способів сформувати максимальну кількість ( $5$ ) груп такий:

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

Приклад 1

Приклад 2