堆堆的击剑平台

众所周知，网安组的堆堆大佬热爱击剑活动，堆堆已经厌倦了普通的击剑平台，他建立了一种特别的击剑平台。

可以把这个击剑平台看作一个数轴，在这个击剑平台上分布了n个击剑手，第i个击剑手站在整数坐标xi处，击剑手可以站在一起，表示他们互相击剑。堆堆作为击剑大师可以进行如下两种操作：将击剑手i向左移动2个单位或向右移动2个单位（即用xi-2或xi + 2替换当前坐标xi）；将击剑手i向左或向右移动1个单位，并为此次操作支付一个硬币。

注意：允许将击剑手移动到任何整数坐标，包括负和零。

堆堆是个老白嫖怪了，他想找到让n个击剑手移动到一个坐标击剑所需的最小硬币总数（即在一些移动序列之后所有xi应该相等）。

Input

输入的第一行包含一个整数n（1≤n≤100） - 击剑手的总数。

输入的第二行包含n个整数x1，x2，…，xn（1≤xi≤10^9），其中xi是第i个击剑手的坐标。

Output

输出一个整数

将所有n个击剑手移动到同一坐标所需的最小硬币总数。

Samples

3
1 2 3

1

5
2 2 2 3 3

2

Note

在第一个例子中，你需要将第一个击剑手向左移动2，将第二个击剑手向左移动1，或者将第三个击剑手向右移动2，将第二个击剑手向右移动1，这样答案就是1。 在第二个例子中，你需要移动两个坐标为7的击剑手，所以答案是2。