E. Squares and not squares

Ann 和 Borya 有 #cf_span[n] 堆糖果，且 #cf_span[n] 是偶数。第 #cf_span[i] 堆中有 #cf_span[ai] 颗糖果。 Ann 喜欢是某个整数平方的数，而 Borya 不喜欢是任何整数平方的数。在一次操作中，两人可以选择一堆糖果，向其中添加一颗糖果（这颗糖果是新的，不属于其他堆）或从中移除一颗糖果（前提是该堆至少有一颗糖果）。 求出最少需要多少次操作，才能使得恰好 #cf_span[n / 2] 堆糖果的数量是某个整数的平方，且恰好 #cf_span[n / 2] 堆糖果的数量不是任何整数的平方。 第一行包含一个 *偶数* 整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 200 000]) —— 糖果堆的数量。 第二行包含一个整数序列 #cf_span[a1, a2, ..., an] (#cf_span[0 ≤ ai ≤ 109]) —— 每堆糖果的数量。 请输出使恰好 #cf_span[n / 2] 堆糖果的数量是某个整数的平方，且恰好 #cf_span[n / 2] 堆糖果的数量不是任何整数的平方所需的最少操作步数。如果条件已满足，请输出 _0_。 在第一个例子中，你可以在两步内满足条件：每步向第二堆添加一颗糖果。之后，第二堆的糖果数变为 #cf_span[16]。此时，Ann 和 Borya 将拥有两堆糖果数量为整数平方的堆（第二堆和第四堆），以及两堆糖果数量不是任何整数平方的堆（第一堆和第三堆）。 在第二个例子中，你需要向任意三堆各添加两颗糖果。 ## Input 第一行包含一个 *偶数* 整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 200 000]) —— 糖果堆的数量。第二行包含一个整数序列 #cf_span[a1, a2, ..., an] (#cf_span[0 ≤ ai ≤ 109]) —— 每堆糖果的数量。 ## Output 请输出使恰好 #cf_span[n / 2] 堆糖果的数量是某个整数的平方，且恰好 #cf_span[n / 2] 堆糖果的数量不是任何整数的平方所需的最少操作步数。如果条件已满足，请输出 _0_。 [samples] ## Note 在第一个例子中，你可以在两步内满足条件：每步向第二堆添加一颗糖果。之后，第二堆的糖果数变为 #cf_span[16]。此时，Ann 和 Borya 将拥有两堆糖果数量为整数平方的堆（第二堆和第四堆），以及两堆糖果数量不是任何整数平方的堆（第一堆和第三堆）。在第二个例子中，你需要向任意三堆各添加两颗糖果。

**Definitions** Let $ n \in \mathbb{Z} $ be an even integer, $ 2 \leq n \leq 200{,}000 $. Let $ A = (a_1, a_2, \dots, a_n) $, where $ a_i \in \mathbb{Z}_{\geq 0} $, denote the number of candies in each pile. Let $ S \subseteq \mathbb{Z}_{\geq 0} $ be the set of perfect squares: $ S = \{ k^2 \mid k \in \mathbb{Z}, k \geq 0 \} $. **Constraints** 1. $ n $ is even. 2. For all $ i \in \{1, \dots, n\} $, $ 0 \leq a_i \leq 10^9 $. **Objective** Determine the minimum number of moves (each move: add 1 or remove 1 candy from a pile) to achieve exactly $ \frac{n}{2} $ piles with $ a_i \in S $ and exactly $ \frac{n}{2} $ piles with $ a_i \notin S $. For each pile $ i $: - If $ a_i \in S $, it is *already good* for Ann; to make it *bad*, remove $ a_i $ candies (cost: $ a_i $) or change it to the nearest non-square (cost: $ \min(|a_i - s|) $ over $ s \notin S $, $ s \geq 0 $). - If $ a_i \notin S $, it is *already good* for Borya; to make it *good for Ann*, change it to the nearest perfect square (cost: $ \min(|a_i - s|) $ over $ s \in S $). Define: - $ C_{\text{to\_square}}(i) = \min_{s \in S} |a_i - s| $ for $ a_i \notin S $ - $ C_{\text{to\_non\_square}}(i) = \min_{s \notin S} |a_i - s| $ for $ a_i \in S $ Let: - $ G_A = \{ i \mid a_i \in S \} $, size $ g = |G_A| $ - $ G_B = \{ i \mid a_i \notin S \} $, size $ n - g $ We need to convert exactly $ \frac{n}{2} - g $ piles from $ G_B $ to squares (if $ g < \frac{n}{2} $), or $ g - \frac{n}{2} $ piles from $ G_A $ to non-squares (if $ g > \frac{n}{2} $). Let $ d = \frac{n}{2} - g $. - If $ d > 0 $: convert $ d $ piles from $ G_B $ to squares → choose $ d $ piles with smallest $ C_{\text{to\_square}}(i) $ - If $ d < 0 $: convert $ |d| $ piles from $ G_A $ to non-squares → choose $ |d| $ piles with smallest $ C_{\text{to\_non\_square}}(i) $ **Objective Function** $$ \min \sum_{\text{selected } i} \text{cost}(i) $$ where the selection is the $ |d| $ cheapest conversions from the appropriate group.