제곱수와 제곱수가 아닌 수

Ann and Borya에게는 사탕이 든 n개의 더미가 있으며, n은 짝수이다. 번호가 i인 더미에는 ai개의 사탕이 있다.

Ann은 어떤 정수의 제곱인 수를 좋아하고, Borya는 어떤 정수의 제곱인 수를 좋아하지 않는다. 한 번의 이동에서 이들은 사탕 더미 하나를 골라 사탕 하나를 추가하거나(이 사탕은 새것이며 다른 어떤 더미에도 속해 있지 않다), 사탕 하나를 제거할 수 있다(이 더미에 적어도 하나의 사탕이 있는 경우에만 가능하다).

정확히 n / 2개의 더미에 든 사탕의 개수가 어떤 정수의 제곱이 되고, 정확히 n / 2개의 더미에 든 사탕의 개수가 어떤 정수의 제곱도 아니게 만드는 데 필요한 이동 횟수의 최솟값을 구한다.

첫째 줄에 사탕 더미의 개수를 나타내는 하나의 짝수 n (2 ≤ n ≤ 200 000)이 주어진다.

둘째 줄에 각 더미에 든 사탕의 개수를 나타내는 정수열 a1, a2, ..., an (0 ≤ ai ≤ 109)가 주어진다.

정확히 n / 2개의 더미에 든 사탕의 개수가 어떤 정수의 제곱이 되고, 정확히 n / 2개의 더미에 든 사탕의 개수가 어떤 정수의 제곱도 아니게 만드는 데 필요한 단계 수의 최솟값을 출력한다. 조건이 이미 충족되어 있다면 0을 출력한다.

첫 번째 예제에서는 두 번의 이동으로 조건을 충족할 수 있다. 각 이동에서 두 번째 더미에 사탕 하나를 추가해야 한다. 그러면 두 번째 더미의 크기는 16이 된다. 그 후 Borya and Ann에게는 사탕의 개수가 정수의 제곱인 더미가 두 개(두 번째와 네 번째 더미), 사탕의 개수가 어떤 정수의 제곱도 아닌 더미가 두 개(첫 번째와 세 번째 더미) 있게 된다.

두 번째 예제에서는 아무 세 더미에 각각 사탕 두 개를 추가해야 한다.