U503858 走地鸡分组

>在你的帮助下，SCUTkk 历经千辛万苦，终于带领 SCUT 散养走地鸡大军逃出了平面世界。接下来，你们继续踏上了旅途。

但自从逃出平面世界以来， SCUT 的散养走地鸡大军已经很久没有遇遭到过大型战斗了，这让 SCUTkk 很有危机感，于是它决定将整个走地鸡大军分成若干个小组进行特训。SCUTkk 希望分出尽可能**最多**的小组，这样才能对每个小组进行更加精细的训练，从而最大化大军的战斗力。 它的分组流程如下：首先，SCUTkk 会命令所有的 $n$ 只走地鸡站成一排，并给每只走地鸡一个整数作为编号（不同位置的两只走地鸡编号**可能相同**）。然后，SCUTkk 会将走地鸡队列分成若干位置连续的段，每一段都会成为一个小组。 作为一种神奇的生物，走地鸡有一种奇异的特性：如果一个小组里有任何一种编号的走地鸡数量是**奇数**，那么它们就会互相看对方不顺眼并**打一架**；而如果一种编号的走地鸡数量是**偶数**，它们就会**相安无事**。 现在所有走地鸡已经站成了一排，并都获得了自己的编号。SCUTkk 不希望看到走地鸡大军发生任何内斗，因此它决定任命你为大军的参谋，希望你能求出在**不发生内斗**的情况下，分出小组的**最大数量**是多少。

第一行一个整数 $n$ ($1 \le n \le {10^5}$)，表示大军中走地鸡的数量。 第二行一个包含 $n$ 个整数的数列 $a$ ($1 \le a_i \le {10^6}$)，$a_i$ 表示排第 $i$ 位的走地鸡的编号。

一行一个整数 $x$ ，表示最多能划分出的小队数量。 **注意：** 一个分组方案是合法的，当且仅当每只走地鸡都属于**恰好一个**小组。 保证至少存在一种合法的分组方案。

第一组样例可以划分为 1 1 | 2 2 | 3 3 三个小组。 第二组样例只能使所有走地鸡分入同一个小组中，才能满足每一种编号的数量都是偶数。 可以证明，无法划分出更多的小组。