数轴上有 n 个筹码,第 i 个筹码的初始坐标为 x_i。多个筹码可以处于同一个坐标。
你可以对任意筹码执行以下两种操作(执行次数不限):
将筹码向左或向右移动 2 个单位,该操作免费(即坐标变为 x_i-2 或 x_i+2);
将筹码向左或向右移动 1 个单位,该操作需要花费 1 个硬币(即坐标变为 x_i-1 或 x_i+1)。
注意,允许将筹码移动到任意整数坐标,包括负数和零。
请问,将所有 n 个筹码移动到同一个坐标,最少需要花费多少个硬币?
第一行包含一个整数 n(1 <= n <= 100),表示筹码的数量。
第二行包含 n 个整数 x_1, x_2, ..., x_n(1 <= x_i <= 10^9),其中 xi 是第 i 个筹码的坐标。
输出一个整数,表示将所有筹码移动到同一坐标所需的最少硬币数。
3 1 2 3
1
5 2 2 2 3 3
2
【数据范围】
1 <= n <= 100,1 <= x_i <= 10^9
【样例说明】
在第一组样例中,一种最优方案是:将第一个筹码向右移动 2 个单位(免费),将第二个筹码向右移动 1 个单位(花费 1 枚硬币),所有筹码最终汇聚在坐标 3,最少花费为 1。
在第二组样例中,最优方案是将两个坐标为 3 的筹码分别向左移动 1 个单位(共花费 2 枚硬币),所有筹码最终汇聚在坐标 2,最少花费为 2。