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

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

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

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

Вхідні дані

Перший рядок містить число n (2 ≤ n ≤ 1000). Другий рядок містить 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

Приклади