题目内容

魔法师有 $n$ 颗魔力水晶，第 $i$ 颗的初始魔力值为 $a_i$。他可以对任意水晶施展强化魔法：选择一颗水晶，为其注入一个正整数 $x$，使其魔力值增加 $x$，施法消耗的魔力等于强化后该水晶的魔力值（即 $a_i+x$）。为了完成一个强大的仪式，他需要让所有水晶的魔力值具有相同的“魔力极性”：魔力极性由魔力值除以 2 的余数决定（余 0 为阳，余 1 为阴）。魔法师希望以最小的总消耗，使得所有水晶的极性全部变为阳，或者全部变为阴。请计算最小总消耗。

水晶的数量 $n$ 不超过 10^5，每颗水晶的初始魔力值 $a_i$ 是不超过 10^9 的正整数。

输入描述

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示水晶的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，表示每颗水晶的初始魔力值，相邻整数之间用一个空格分隔。

输出描述