Ann 和 Borya 有 n 堆糖果,n 是偶数。有一堆ai糖果,编号为i。
Ann 喜欢某个整数的平方的数字,而 Borya 不喜欢任何整数的平方的数字。在一次移动过程中,人们可以选择一些糖果堆,并向其中添加一颗糖果(该糖果是新的,不属于任何其他堆)或移除一颗糖果(如果这一堆中至少有一颗糖果)。
找出使恰好 n / 2 堆包含的糖果数量为某个整数的平方和恰好 n / 2 堆包含的糖果数量不是任何整数的平方所需的最小移动次数。
输入
第一行包含一个偶数 n (2 ≤ n ≤ 200 000) — 糖果堆的数量。
第二行包含整数序列 a1, a2, ..., an (0 ≤ ai ≤ 109) - 每堆糖果的数量。
输出
输出使恰好 n / 2 堆包含的糖果数量为某个整数的平方并且恰好 n / 2 堆包含的糖果数量不是任何整数的平方所需的最小步骤数。如果条件已经满足,则输出 0。
示例
输入 #1
4 12 14 30 4
输出 #1
2
输入 #2
6 0 0 0 0 0 0
输出 #2
6
输入 #3
6 120 110 23 34 25 45
输出 #3
3
输入#4
10 121 56 78 81 45 100 1 0 54 78
输出#4
0
注意
在第一个示例中,您可以通过两步满足条件。每次移动时,您都应该在第二堆中添加一颗糖果。之后第二堆的大小变为 16。之后,Borya 和 Ann 将有两堆糖果数量为整数的平方(第二堆和第四堆)和两堆糖果的数量不是任何整数的平方(第一堆和第三堆)。
在第二个示例中,您应该向任意三堆添加两颗糖果。