{"raw_statement":[{"iden":"statement","content":"Ann and Borya have _n_ piles with candies and _n_ is even number. There are _a__i_ candies in pile with number _i_.\n\nAnn likes numbers which are square of some integer and Borya doesn't like numbers which are square of any integer. During one move guys can select some pile with candies and add one candy to it (this candy is new and doesn't belong to any other pile) or remove one candy (if there is at least one candy in this pile).\n\nFind out minimal number of moves that is required to make exactly _n_ / 2 piles contain number of candies that is a square of some integer and exactly _n_ / 2 piles contain number of candies that is not a square of any integer."},{"iden":"input","content":"First line contains one **even** integer _n_ (2 ≤ _n_ ≤ 200 000) — number of piles with candies.\n\nSecond line contains sequence of integers _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ ≤ 109) — amounts of candies in each pile."},{"iden":"output","content":"Output minimal number of steps required to make exactly _n_ / 2 piles contain number of candies that is a square of some integer and exactly _n_ / 2 piles contain number of candies that is not a square of any integer. If condition is already satisfied output _0_."},{"iden":"examples","content":"Input\n\n4\n12 14 30 4\n\nOutput\n\n2\n\nInput\n\n6\n0 0 0 0 0 0\n\nOutput\n\n6\n\nInput\n\n6\n120 110 23 34 25 45\n\nOutput\n\n3\n\nInput\n\n10\n121 56 78 81 45 100 1 0 54 78\n\nOutput\n\n0"},{"iden":"note","content":"In first example you can satisfy condition in two moves. During each move you should add one candy to second pile. After it size of second pile becomes 16. After that Borya and Ann will have two piles with number of candies which is a square of integer (second and fourth pile) and two piles with number of candies which is not a square of any integer (first and third pile).\n\nIn second example you should add two candies to any three piles."}],"translated_statement":[{"iden":"statement","content":"Ann 和 Borya 有 #cf_span[n] 堆糖果，且 #cf_span[n] 是偶数。第 #cf_span[i] 堆中有 #cf_span[ai] 颗糖果。\n\nAnn 喜欢是某个整数平方的数，而 Borya 不喜欢是任何整数平方的数。在一次操作中，两人可以选择一堆糖果，向其中添加一颗糖果（这颗糖果是新的，不属于其他堆）或从中移除一颗糖果（前提是该堆至少有一颗糖果）。\n\n求出最少需要多少次操作，才能使得恰好 #cf_span[n / 2] 堆糖果的数量是某个整数的平方，且恰好 #cf_span[n / 2] 堆糖果的数量不是任何整数的平方。\n\n第一行包含一个 *偶数* 整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 200 000]) —— 糖果堆的数量。\n\n第二行包含一个整数序列 #cf_span[a1, a2, ..., an] (#cf_span[0 ≤ ai ≤ 109]) —— 每堆糖果的数量。\n\n请输出使恰好 #cf_span[n / 2] 堆糖果的数量是某个整数的平方，且恰好 #cf_span[n / 2] 堆糖果的数量不是任何整数的平方所需的最少操作步数。如果条件已满足，请输出 _0_。\n\n在第一个例子中，你可以在两步内满足条件：每步向第二堆添加一颗糖果。之后，第二堆的糖果数变为 #cf_span[16]。此时，Ann 和 Borya 将拥有两堆糖果数量为整数平方的堆（第二堆和第四堆），以及两堆糖果数量不是任何整数平方的堆（第一堆和第三堆）。\n\n在第二个例子中，你需要向任意三堆各添加两颗糖果。"},{"iden":"input","content":"第一行包含一个 *偶数* 整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 200 000]) —— 糖果堆的数量。第二行包含一个整数序列 #cf_span[a1, a2, ..., an] (#cf_span[0 ≤ ai ≤ 109]) —— 每堆糖果的数量。"},{"iden":"output","content":"请输出使恰好 #cf_span[n / 2] 堆糖果的数量是某个整数的平方，且恰好 #cf_span[n / 2] 堆糖果的数量不是任何整数的平方所需的最少操作步数。如果条件已满足，请输出 _0_。"},{"iden":"examples","content":"输入412 14 30 4输出2输入60 0 0 0 0 0输出6输入6120 110 23 34 25 45输出3输入10121 56 78 81 45 100 1 0 54 78输出0"},{"iden":"note","content":"在第一个例子中，你可以在两步内满足条件：每步向第二堆添加一颗糖果。之后，第二堆的糖果数变为 #cf_span[16]。此时，Ann 和 Borya 将拥有两堆糖果数量为整数平方的堆（第二堆和第四堆），以及两堆糖果数量不是任何整数平方的堆（第一堆和第三堆）。在第二个例子中，你需要向任意三堆各添加两颗糖果。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be an even integer, $ 2 \\leq n \\leq 200{,}000 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $, where $ a_i \\in \\mathbb{Z}_{\\geq 0} $, denote the number of candies in each pile.  \nLet $ S \\subseteq \\mathbb{Z}_{\\geq 0} $ be the set of perfect squares: $ S = \\{ k^2 \\mid k \\in \\mathbb{Z}, k \\geq 0 \\} $.  \n\n**Constraints**  \n1. $ n $ is even.  \n2. For all $ i \\in \\{1, \\dots, n\\} $, $ 0 \\leq a_i \\leq 10^9 $.  \n\n**Objective**  \nDetermine 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 $.  \n\nFor each pile $ i $:  \n- 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 $).  \n- 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 $).  \n\nDefine:  \n- $ C_{\\text{to\\_square}}(i) = \\min_{s \\in S} |a_i - s| $ for $ a_i \\notin S $  \n- $ C_{\\text{to\\_non\\_square}}(i) = \\min_{s \\notin S} |a_i - s| $ for $ a_i \\in S $  \n\nLet:  \n- $ G_A = \\{ i \\mid a_i \\in S \\} $, size $ g = |G_A| $  \n- $ G_B = \\{ i \\mid a_i \\notin S \\} $, size $ n - g $  \n\nWe 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} $).  \n\nLet $ d = \\frac{n}{2} - g $.  \n\n- If $ d > 0 $: convert $ d $ piles from $ G_B $ to squares → choose $ d $ piles with smallest $ C_{\\text{to\\_square}}(i) $  \n- If $ d < 0 $: convert $ |d| $ piles from $ G_A $ to non-squares → choose $ |d| $ piles with smallest $ C_{\\text{to\\_non\\_square}}(i) $  \n\n**Objective Function**  \n$$\n\\min \\sum_{\\text{selected } i} \\text{cost}(i)\n$$  \nwhere the selection is the $ |d| $ cheapest conversions from the appropriate group.","simple_statement":null,"has_page_source":false}