← 返回题目列表

Codeforces · 898/E

E. 正方形和非正方形

中文机器翻译题面 查看原题

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 将有两堆糖果数量为整数的平方(第二堆和第四堆)和两堆糖果的数量不是任何整数的平方(第一堆和第三堆)。

在第二个示例中,您应该向任意三堆添加两颗糖果。