← 返回题目列表

Codeforces · 1213/A

A. 筹码移动

中文机器翻译题面 查看原题

您在数轴上获得了 $$$n$$$ 筹码。第 $$$i$$$ 个筹码放置在整数坐标 $$$x_i$$$ 处。有些芯片可以具有相同的坐标。

您可以在任何筹码上执行以下两种类型的移动任意(可能为零)次:

- 将芯片 $$$i$$$ 向左移动 $$$2$$$ 或向右移动 $$$2$$$(即将当前坐标 $$$x_i$$$ 替换为 $$$x_i - 2$$$ 或 $$$x_i + 2$$$);
- 将筹码 $$$i$$$ 向左移动 $$$1$$$ 或向右移动 $$$1$$$,并为此移动支付一枚硬币(即将当前坐标 $$$x_i$$$ 替换为 $$$x_i - 1$$$ 或 $$$x_i + 1$$$)。

请注意,允许将芯片移动到任何整数坐标,包括负数和零。

您的任务是找到将所有 $$$n$$$ 筹码移动到同一坐标所需的最小硬币总数(即,经过一系列移动后,所有 $$$x_i$$$ 应相等)。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 芯片数量。

输入的第二行包含 $$$n$$$ 整数 $$$x_1, x_2, \dots, x_n$$$ ($$$1 \le x_i \le 10^9$$$),其中 $$$x_i$$$ 是第 $$$i$$$ 个芯片的坐标。

输出

打印一个整数 — 将所有 $$$n$$$ 筹码移动到同一坐标所需的最小硬币总数。

示例

输入 #1

3
1 2 3

输出 #1

1

输入 #2

5
2 2 2 3 3

输出 #2

2

注意

在第一个示例中,您需要将第一个筹码向右移动 $$$2$$$,将第二个筹码向右移动 $$$1$$$,或者将第三个筹码向左移动 $$$2$$$,将第二个筹码向左移动 $$$1$$$,因此答案为 $$$1$$$。

在第二个示例中,您需要将坐标为 $$$3$$$ 的两个芯片向左移动 $$$1$$$,因此答案为 $$$2$$$。