#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000000 + 7;
const long long MOD1 = 998244353;
long long mod(long long x) { return (x % MOD + MOD) % MOD; }
long long mul(long long a, long long b) { return mod(mod(a) * mod(b)); }
string itos(long long s) {
  string str = to_string(s);
  return str;
}
long long stoi2(string s) {
  long long a = atoi(s.c_str());
  return a;
}
long long powerm(long long a, long long b, long long MOD) {
  a %= MOD;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return res;
}
long long power(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}
bool isSubSequence(string str1, string str2, int m, int n) {
  if (m == 0) return true;
  if (n == 0) return false;
  if (str1[m - 1] == str2[n - 1])
    return isSubSequence(str1, str2, m - 1, n - 1);
  return isSubSequence(str1, str2, m, n - 1);
}
bool ispalindrome(long long len, string str) {
  for (int i = 0; i < len / 2; i++) {
    if (str[i] != str[len - 1 - i]) {
      return false;
    }
  }
  return true;
}
long long binarySearch(long long a[], long long low, long long high,
                       long long key) {
  while (low <= high) {
    long long mid = (low + high) / 2;
    if (a[mid] < key) {
      low = mid + 1;
    } else if (a[mid] > key) {
      high = mid - 1;
    } else {
      return mid;
    }
  }
  return -1;
}
inline bool isPowerOfTwo(long long x) {
  return ((1LL << (long long)log2(x)) == x);
}
long long isprime(long long N) {
  if (N < 2 || (!(N & 1) && N != 2)) return 0;
  for (long long i = 3; i * i <= N; i += 2) {
    if (!(N % i)) return 0;
  }
  return 1;
}
vector<long long> factor;
void factors(long long n) {
  for (long long i = 1; i <= sqrt(n); i++) {
    if (n % i == 0) {
      if (i == n / i)
        factor.push_back(i);
      else {
        factor.push_back(i);
        factor.push_back(n / i);
      }
    }
  }
  sort((factor).begin(), (factor).end());
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (a / gcd(a, b)) * b; }
bool isvalid(long long i, long long j, long long n) {
  if (i >= 0 && i < n && j >= 0 && j < n) return true;
  return false;
}
long long dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
long long dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
long long binarytodecimal(string n) {
  string num = n;
  long long dec_value = 0;
  long long base = 1;
  long long len = num.length();
  for (int i = len - 1; i >= 0; i--) {
    if (num[i] == '1') dec_value += base;
    base = base * 2;
  }
  return dec_value;
}
string dtb(long long n) {
  string s = "";
  while (n > 0) {
    if (n % 2 == 0)
      s.push_back('0');
    else
      s.push_back('1');
    n /= 2;
  }
  reverse((s).begin(), (s).end());
  return s;
}
vector<long long> seive;
void Seive() {
  const long long maxn = 1e6 + 5;
  seive.resize(maxn);
  for (long long i = (long long)0; i < (long long)maxn; i++) seive[i] = i;
  for (long long i = 2; i <= maxn; i += 2) seive[i] = 2;
  seive[1] = -1;
  seive[0] = -1;
  for (long long i = 3; i <= maxn; i += 2)
    if (i == seive[i])
      for (long long j = i * i; j < maxn; j += i)
        if (seive[j] == j) seive[j] = i;
}
inline bool isSquare(long long x) {
  long long s = sqrt(x);
  return (s * s == x);
}
int main() {
  long long n;
  cin >> n;
  long long ar[n];
  for (long long i = (long long)0; i < (long long)n; i++) cin >> ar[i];
  vector<long long> a, b, c3;
  long long z = 0, z2 = 0;
  for (long long i = (long long)0; i < (long long)n; i++) {
    long long r = sqrt(ar[i]);
    if (isSquare(ar[i])) {
      z++;
      a.push_back(1 + (ar[i] == 0));
    } else {
      b.push_back(min(ar[i] - r * r, (r + 1) * (r + 1) - ar[i]));
      z2++;
    }
  }
  long long ans = 0;
  if (z >= z2) {
    sort(a.begin(), a.end());
    for (long long i = (long long)0; i < (long long)n / 2 - z2; i++)
      ans += a[i];
    cout << ans;
  } else {
    sort(b.begin(), b.end());
    for (long long i = (long long)0; i < (long long)n / 2 - z; i++) ans += b[i];
    cout << ans;
  }
}

### Prompt

Develop a solution in cpp to the problem described below:

Ann and Borya have n piles with candies and n is even number. There are ai candies in pile with number i.

Ann 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). 

Find 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.

Input

First line contains one even integer n (2 ≤ n ≤ 200 000) — number of piles with candies.

Second line contains sequence of integers a1, a2, ..., an (0 ≤ ai ≤ 109) — amounts of candies in each pile.

Output

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.

Examples

Input

4
12 14 30 4


Output

2


Input

6
0 0 0 0 0 0


Output

6


Input

6
120 110 23 34 25 45


Output

3


Input

10
121 56 78 81 45 100 1 0 54 78


Output

0

Note

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).

In second example you should add two candies to any three piles.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000000 + 7;
const long long MOD1 = 998244353;
long long mod(long long x) { return (x % MOD + MOD) % MOD; }
long long mul(long long a, long long b) { return mod(mod(a) * mod(b)); }
string itos(long long s) {
  string str = to_string(s);
  return str;
}
long long stoi2(string s) {
  long long a = atoi(s.c_str());
  return a;
}
long long powerm(long long a, long long b, long long MOD) {
  a %= MOD;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return res;
}
long long power(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}
bool isSubSequence(string str1, string str2, int m, int n) {
  if (m == 0) return true;
  if (n == 0) return false;
  if (str1[m - 1] == str2[n - 1])
    return isSubSequence(str1, str2, m - 1, n - 1);
  return isSubSequence(str1, str2, m, n - 1);
}
bool ispalindrome(long long len, string str) {
  for (int i = 0; i < len / 2; i++) {
    if (str[i] != str[len - 1 - i]) {
      return false;
    }
  }
  return true;
}
long long binarySearch(long long a[], long long low, long long high,
                       long long key) {
  while (low <= high) {
    long long mid = (low + high) / 2;
    if (a[mid] < key) {
      low = mid + 1;
    } else if (a[mid] > key) {
      high = mid - 1;
    } else {
      return mid;
    }
  }
  return -1;
}
inline bool isPowerOfTwo(long long x) {
  return ((1LL << (long long)log2(x)) == x);
}
long long isprime(long long N) {
  if (N < 2 || (!(N & 1) && N != 2)) return 0;
  for (long long i = 3; i * i <= N; i += 2) {
    if (!(N % i)) return 0;
  }
  return 1;
}
vector<long long> factor;
void factors(long long n) {
  for (long long i = 1; i <= sqrt(n); i++) {
    if (n % i == 0) {
      if (i == n / i)
        factor.push_back(i);
      else {
        factor.push_back(i);
        factor.push_back(n / i);
      }
    }
  }
  sort((factor).begin(), (factor).end());
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (a / gcd(a, b)) * b; }
bool isvalid(long long i, long long j, long long n) {
  if (i >= 0 && i < n && j >= 0 && j < n) return true;
  return false;
}
long long dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
long long dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
long long binarytodecimal(string n) {
  string num = n;
  long long dec_value = 0;
  long long base = 1;
  long long len = num.length();
  for (int i = len - 1; i >= 0; i--) {
    if (num[i] == '1') dec_value += base;
    base = base * 2;
  }
  return dec_value;
}
string dtb(long long n) {
  string s = "";
  while (n > 0) {
    if (n % 2 == 0)
      s.push_back('0');
    else
      s.push_back('1');
    n /= 2;
  }
  reverse((s).begin(), (s).end());
  return s;
}
vector<long long> seive;
void Seive() {
  const long long maxn = 1e6 + 5;
  seive.resize(maxn);
  for (long long i = (long long)0; i < (long long)maxn; i++) seive[i] = i;
  for (long long i = 2; i <= maxn; i += 2) seive[i] = 2;
  seive[1] = -1;
  seive[0] = -1;
  for (long long i = 3; i <= maxn; i += 2)
    if (i == seive[i])
      for (long long j = i * i; j < maxn; j += i)
        if (seive[j] == j) seive[j] = i;
}
inline bool isSquare(long long x) {
  long long s = sqrt(x);
  return (s * s == x);
}
int main() {
  long long n;
  cin >> n;
  long long ar[n];
  for (long long i = (long long)0; i < (long long)n; i++) cin >> ar[i];
  vector<long long> a, b, c3;
  long long z = 0, z2 = 0;
  for (long long i = (long long)0; i < (long long)n; i++) {
    long long r = sqrt(ar[i]);
    if (isSquare(ar[i])) {
      z++;
      a.push_back(1 + (ar[i] == 0));
    } else {
      b.push_back(min(ar[i] - r * r, (r + 1) * (r + 1) - ar[i]));
      z2++;
    }
  }
  long long ans = 0;
  if (z >= z2) {
    sort(a.begin(), a.end());
    for (long long i = (long long)0; i < (long long)n / 2 - z2; i++)
      ans += a[i];
    cout << ans;
  } else {
    sort(b.begin(), b.end());
    for (long long i = (long long)0; i < (long long)n / 2 - z; i++) ans += b[i];
    cout << ans;
  }
}

```