Ann and Borya have n piles with candies and n is even number. There are a_{i} 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 a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^9) — 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.

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))
squares = []
not_squares = []
for i in range(n):
	cur = a[i]
	if int(cur ** 0.5) ** 2 == cur:
		squares.append(cur)
	else:
		not_squares.append(cur)
num_move = (len(squares) - len(not_squares)) // 2
if num_move == 0:
	print(0)
elif num_move > 0:
	count_0 = squares.count(0)
	moves = [1] * (len(squares) - count_0) + [2] * count_0
	print(sum(moves[:num_move]))
else:
	moves = [None] * len(not_squares)
	for i in range(len(not_squares)):
		cur = not_squares[i]
		sqrt_cur = int(cur ** 0.5)
		moves[i] = min(cur - sqrt_cur ** 2, (sqrt_cur + 1) ** 2 - cur)
	moves.sort()
	print(sum(moves[:-num_move]))


n = int(input())
a = map(int, input().split())
x = []
for i in a:
	r = int(i ** 0.5)
	x.append((min(i - r * r, (r + 1) ** 2 - i), i))
x.sort()
if x[n // 2][0] != 0:
	ans = 0
	for i in range(0, n // 2):
		ans += x[i][0]
	print(ans)
else:
	(ans, i) = (0, n // 2)
	while i < n and x[i][0] == 0:
		if x[i][1] == 0:
			ans += 2
		else:
			ans += 1
		i += 1
		i
	print(ans)


def ispow(c):
	x = int(c ** 0.5)
	return x * x == c or (x + 1) * (x + 1) == c or (x + 2) * (x + 2) == c
n = int(input())
a = list(map(int, input().split()))
kb = []
nk = []
for i in range(n):
	if ispow(a[i]):
		if a[i] == 0:
			kb.append(2)
		else:
			kb.append(1)
	else:
		c = int(a[i] ** 0.5)
		x = abs(c * c - a[i])
		y = abs((c + 1) * (c + 1) - a[i])
		nk.append(min(x, y))
if len(kb) > len(nk):
	kb.sort()
	s = 0
	for i in range(len(kb) - n // 2):
		s += kb[i]
	print(s)
elif len(kb) == len(nk):
	print(0)
else:
	nk.sort()
	s = 0
	for i in range(len(nk) - n // 2):
		s += nk[i]
	print(s)


from sys import stdin, stdout
from math import sqrt
import math
import heapq
from itertools import accumulate

def near_sq(num):
	return round(sqrt(num)) ** 2
N = int(input())
arr = [int(x) for x in stdin.readline().split()]
sqr = 0
non = 0
sqr_mini = []
non_mini = []
for num in arr:
	p = near_sq(num)
	if p - num == 0:
		sqr += 1
		if num == 0:
			sqr_mini.append(2)
		else:
			sqr_mini.append(1)
	else:
		non += 1
		non_mini.append(abs(p - num))
if sqr == non:
	print(0)
	quit()
res = 0
half = N // 2
if sqr > non:
	required = sqr - half
	sqr_mini.sort()
	res = sum(sqr_mini[:required])
elif non > sqr:
	required = non - half
	non_mini.sort()
	res = sum(non_mini[:required])
print(res)


n = int(input())
li = input().strip().split(' ')
nums = []
ct = 0
zeros = 0
for i in li:
	i = int(i)
	if i == 0:
		zeros += 1
	if round(i ** 0.5) ** 2 == i:
		ct += 1
	tmp = int(i ** 0.5)
	nums.append(min(i - tmp * tmp, (tmp + 1) ** 2 - i))
nums.sort()
half = int(n / 2)
if ct <= half:
	print(sum(nums[:half]))
else:
	rst = ct - half
	if zeros > half:
		rst += zeros - half
	print(rst)


n = int(input())
a = [int(i) for i in input().split()]
(b, v, ans) = ([], [], 0)
for i in a:
	c = int(i ** (1 / 2))
	if c * c == i or (c + 1) * (c + 1) == i or (c - 1) * (c - 1) == i:
		b.append(i)
b.sort(reverse=True)
for i in range(len(b) - n // 2):
	if b[i] == 0:
		ans += 2
	else:
		ans += 1
for i in a:
	c = int(i ** (1 / 2))
	if c * c == i or (c + 1) * (c + 1) == i or (c - 1) * (c - 1) == i:
		continue
	v.append(min(i - c * c, (c + 1) * (c + 1) - i))
v.sort()
for i in range(n // 2 - len(b)):
	ans += v[i]
print(ans)


n = int(input())
arr = list(map(int, input().strip().split(' ')))
sq = 0
nsq = 0
sqq = []
nsqq = []
for i in arr:
	t = int(i ** 0.5)
	if t * t == i:
		sq += 1
		sqq.append(i)
	else:
		nsq += 1
		nsqq.append(i)
if sq == nsq:
	print(0)
elif sq > nsq:
	d = sq - n // 2
	cost = []
	for i in sqq:
		if i != 0:
			cost.append(1)
		else:
			cost.append(2)
	cost.sort()
	s = 0
	for i in range(d):
		s += cost[i]
	print(s)
else:
	d = nsq - n // 2
	cost = []
	for i in nsqq:
		t = int(i ** 0.5)
		pp = t * t
		ppp = (t + 1) * (t + 1)
		cost.append(min(abs(i - pp), abs(i - ppp)))
	cost.sort()
	s = 0
	for i in range(d):
		s += cost[i]
	print(s)


d = lambda x: abs(int(x ** 0.5 + 0.5) ** 2 - x)
n = int(input()) // 2
a = sorted([[d(int(x)), int(x)] for x in input().split()])
print(sum((i[0] for i in a[:n])) + sum(((i[0] == 0) + (i[1] == 0) for i in a[n:])))


n = input()
m = input().split()
a = []
b = []
for s in m:
	i = int(s)
	if int(i ** (1 / 2)) ** 2 == i:
		a.append(i)
	else:
		b.append(i)
if len(a) >= len(b):
	ans = 0
	a = sorted(a)
	for i in range(len(a) - 1, len(a) - (len(a) - len(b)) // 2 - 1, -1):
		if a[i] != 0:
			ans += 1
		else:
			ans += 2
	print(ans)
else:
	k = 0
	r = len(b) - len(a)
	r = int(r / 2)
	a = []
	for i in b:
		q = int(i ** (1 / 2))
		q1 = q ** 2
		q2 = (q + 1) ** 2
		q1 = i - q1
		q2 = q2 - i
		if q1 < q2:
			q = q1
		else:
			q = q2
		a.append(q)
	print(sum(sorted(a)[:r]))


n = int(input())
p = []
m = list(map(int, input().split()))
from math import floor, ceil
for i in m:
	if i ** 0.5 % 1 == 0:
		p.append(0)
	else:
		p.append(min(i - floor(i ** 0.5) ** 2, ceil(i ** 0.5) ** 2 - i))
a = p.count(0)
am = m.count(0)
if n // 2 <= a:
	x = a - n // 2
	dif = a - am
	if dif >= x:
		print(x)
	else:
		print(dif + (x - dif) * 2)
else:
	p.sort()
	k = a - n // 2
	x = a
	ans = 0
	for i in range(a, n // 2):
		ans += p[i]
	print(ans)


import math

def distance(x):
	sqrtFloor = int(math.sqrt(x))
	low = int(math.pow(sqrtFloor, 2))
	high = int(math.pow(sqrtFloor + 1, 2))
	return min(high - x, x - low)
n = int(input())
s = input()
piles = list(map(int, s.split()))
op = []
for i in range(0, n):
	op.append(distance(piles[i]))
op.sort()
result = 0
for i in range(0, int(n / 2)):
	result += op[i]
perfectPositive = 0
perfectZero = 0
for i in range(0, n):
	if distance(piles[i]) == 0:
		if piles[i] == 0:
			perfectZero += 1
		else:
			perfectPositive += 1
while perfectPositive + perfectZero > n / 2:
	if perfectPositive > 0:
		perfectPositive -= 1
		result += 1
	else:
		perfectZero -= 1
		result += 2
print(result)


sq = [i * i for i in range(10 ** 5 + 5)]
a = []
nules = 0
ap = a.append
from bisect import bisect_left
n = int(input()) // 2
for i in map(int, input().split()):
	if i == 0:
		ap(0)
		nules += 1
	else:
		ind = bisect_left(sq, i)
		ap(min(i - sq[ind - 1], sq[ind] - i))
a = sorted(a)
s = sum(a[:n])
if s == 0:
	print(n - a[::-1].index(0) + max(0, nules - n))
else:
	print(s)


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def si():
	return input()

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')

def power_set(L):
	cardinality = len(L)
	n = 2 ** cardinality
	powerset = []
	for i in range(n):
		a = bin(i)[2:]
		subset = []
		for j in range(len(a)):
			if a[-j - 1] == '1':
				subset.append(L[j])
		powerset.append(subset)
	powerset_orderred = []
	for k in range(cardinality + 1):
		for w in powerset:
			if len(w) == k:
				powerset_orderred.append(w)
	return powerset_orderred

def fastPlrintNextLines(a):
	print('\n'.join(map(str, a)))

def sortByFirstAndSecond(A):
	A = sorted(A, key=lambda x: x[0])
	A = sorted(A, key=lambda x: x[1])
	return list(A)
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = 1
for _ in range(t):
	n = ii()
	a = li()
	cnt = 0
	for i in a:
		if i ** (1 / 2) == int(i ** (1 / 2)):
			cnt += 1
	if cnt == n // 2:
		print(0)
		continue
	if cnt > n // 2:
		if a.count(0) <= n // 2:
			print(cnt - n // 2)
		else:
			print(cnt - n // 2 + a.count(0) - n // 2)
		continue
	toadd = [0] * n
	for i in range(n):
		x = int(a[i] ** (1 / 2))
		minsq = x * x
		maxaq = (x + 1) * (x + 1)
		toadd[i] = min(abs(a[i] - minsq), abs(a[i] - maxaq))
	new = []
	for i in toadd:
		if i != 0:
			new.append(i)
	toadd = new[:]
	toadd.sort()
	print(sum(toadd[:n // 2 - cnt]))


n = int(input())
f = lambda x: abs(int(x ** 0.5 + 0.5) ** 2 - x)
a = list(map(lambda x: [f(int(x)), int(x)], input().split()))
a.sort()
ans = sum((i[0] for i in a[:n // 2])) + sum(((i[0] == 0) + (i[1] == 0) for i in a[n // 2:]))
print(ans)


import math
n = int(input())
nums = [int(i) for i in input().split()]
a = [1000000000] * n
zero = 0
s = 0
for i in range(n):
	num = nums[i]
	k = int(math.sqrt(num))
	if k * k == num:
		if num == 0:
			zero += 1
		s += 1
	else:
		a[i] = min(num - k * k, (k + 1) * (k + 1) - num)
ans = 0
if s > n - s:
	delta = (s - (n - s)) // 2
	if delta <= s - zero:
		ans += delta
	else:
		ans += 2 * (delta - (s - zero)) + (s - zero)
else:
	delta = (n - s - s) // 2
	a.sort()
	ans = sum(a[:delta])
print(ans)


T = int(input())
from math import sqrt, floor, ceil

def is_sqrt(x, xx):
	xxx = floor(xx)
	if xx - xxx > 0.7:
		xxx = ceil(xx)
	return xxx * xxx == x
(sq, nsq) = ([], [])
for s in input().split():
	x = int(s)
	xx = sqrt(x)
	if is_sqrt(x, xx):
		a = 1 if x != 0 else 2
		nsq.append(a)
	else:
		(b, c) = (floor(xx), ceil(xx))
		(b, c) = (x - b * b, c * c - x)
		a = b if b < c else c
		sq.append(a)
if len(sq) == len(nsq):
	print(0)
else:
	cont = sq if len(sq) > len(nsq) else nsq
	cont.sort()
	num = len(cont) - T // 2
	print(sum(cont[0:num]))


r = 0
n = int(input())
ps = [int(x) for x in input().split()]
mp = []
for y in ps:
	if y > 0 and y - int(y ** (1 / 2)) ** 2 != 0:
		mp.append(min(abs(y - int(y ** (1 / 2)) ** 2), abs(y - (int(y ** (1 / 2)) + 1) ** 2)))
	elif y > 0 and y - int(y ** (1 / 2)) ** 2 == 0:
		mp.append(-1)
	elif y == 0:
		mp.append(0)

def key(x):
	if x < 0:
		return x + 2
	elif x == 0:
		return x
	else:
		return x + 3
mp.sort(key=key)
if mp[n // 2 - 1] == 0 or mp[n // 2 - 1] == -1:
	for i in range(n // 2, n):
		if mp[i] == 0:
			r += 2
		elif mp[i] == -1:
			r += 1
else:
	r = sum([x for x in mp[:n // 2] if x >= 0])
print(r)


import math as m
n = int(input())
a = [int(z) for z in input().split()]
ans = 0

def sq(a):
	tmp = int(m.sqrt(a))
	s = tmp * tmp
	tmp += 1
	b = tmp * tmp
	if abs(a - s) < abs(a - b):
		return abs(a - s)
	else:
		return abs(a - b)
d = []
for i in range(n):
	d.append((sq(a[i]), a[i]))
d.sort()
for i in range(n // 2):
	ans += d[i][0]
for i in range(n // 2, n):
	if d[i][0] == 0:
		if d[i][1] == 0:
			ans += 2
		else:
			ans += 1
print(ans)


import sys
input = sys.stdin.readline
from collections import *
from bisect import *
n = int(input())
a = list(map(int, input().split()))
l = []
for i in range(10 ** 5):
	l.append(i * i)
s = set(l)
cost1 = []
cost2 = []
for ai in a:
	if ai in s:
		if ai == 0:
			cost1.append(2)
		else:
			cost1.append(1)
	else:
		idx = bisect_right(l, ai)
		cost2.append(min(ai - l[idx - 1], l[idx] - ai))
cost1.sort()
cost2.sort()
if len(cost1) >= len(cost2):
	print(sum(cost1[:len(cost1) - n // 2]))
else:
	print(sum(cost2[:len(cost2) - n // 2]))


n = int(input())
a = list(map(int, input().split()))
(l, p, q) = ([], 0, 0)
for i in a:
	if i == 0:
		p += 1
	else:
		t = int(i ** 0.5)
		s = i - t ** 2
		if s == 0:
			p += 1
			q += 1
		else:
			s = min(s, 2 * t + 1 - s)
			l.append(s)
if p > n // 2:
	p -= n // 2
	if q > p:
		print(p)
	else:
		print(2 * p - q)
elif p == n // 2:
	print(0)
else:
	l.sort()
	s = 0
	p = n // 2 - p
	for i in range(p):
		s += l[i]
	print(s)


import math
n = int(input())
a = list(map(lambda x: [int(x), int(x)], input().split()))
cnt = 0
for i in range(n):
	x = int(math.sqrt(a[i][0]) + 0.5)
	a[i][0] = abs(a[i][0] - x * x)
	if a[i][0] == 0:
		cnt += 1
a.sort()
ans = 0
if cnt > n // 2:
	need = cnt - n // 2
	for i in range(n):
		if need == 0:
			break
		if a[i][0] == 0 and a[i][1] != 0:
			ans += 1
			need -= 1
	for i in range(n):
		if need == 0:
			break
		if a[i][1] == 0:
			ans += 2
			need -= 1
else:
	need = n // 2 - cnt
	for i in range(n):
		if need == 0:
			break
		if a[i][0] != 0:
			ans += a[i][0]
			need -= 1
print(ans)


import math
sop = []
ans = 0

def findclosestsquare(a):
	x = []
	for i in a:
		s = i ** 0.5
		s = round(s)
		x.append((abs(s ** 2 - i), i))
	return x
cases = int(input())
summ = 0
numbers = list(map(int, input().split()))
sop = findclosestsquare(numbers)
sop.sort()

def counter(n, x):
	n2 = n // 2
	ans = 0
	for i in range(n2):
		ans += x[i][0]
	for i in range(n2, n):
		if x[i][0] == 0:
			if x[i][1] == 0:
				ans += 2
			else:
				ans += 1
	return ans
print(counter(cases, sop))


perfectsquares = set((x ** 2 for x in range(10 ** 5 + 1)))
N = int(input())
array = [int(x) for x in input().split()]
(squares, notsquares) = [0, 0]
squarelist = []
notsquarelist = []
for i in array:
	if i in perfectsquares:
		squares += 1
		squarelist.append(i)
	else:
		notsquares += 1
		notsquarelist.append(i)
toadd = []
counter = 0
if notsquares > squares:
	for i in notsquarelist:
		if i ** (1 / 2) - float(i ** (1 / 2)) // 1 < 0.5:
			toadd.append(int(abs(i - (i ** (1 / 2) // 1) ** 2)))
		else:
			toadd.append(int(abs(i - (i ** (1 / 2) // 1 + 1) ** 2)))
	toadd = sorted(toadd)
	counter = sum(toadd[:(notsquares - squares) // 2])
elif squares > notsquares:
	for i in squarelist:
		if i == 0:
			toadd.append(2)
		else:
			toadd.append(1)
	toadd = sorted(toadd)
	counter = sum(toadd[:(squares - notsquares) // 2])
print(int(counter))


n = int(input())
f = lambda x: min(x - int(x ** 0.5) ** 2, (int(x ** 0.5) + 1) ** 2 - x)
a = sorted([[f(int(i)), int(i)] for i in input().split()])
ans = sum((i[0] for i in a[:n // 2])) + sum(((int(i[1] ** 0.5) ** 2 == i[1]) + (i[1] == 0) for i in a[n // 2:]))
print(ans)


import math
n = int(input())
ls = list(map(int, input().split()))
diff_to_square = []
diff_to_non_square = []
for elem in ls:
	sqrt = math.floor(math.sqrt(elem))
	if sqrt * sqrt != elem:
		diff_to_square.append(min(elem - sqrt * sqrt, (sqrt + 1) * (sqrt + 1) - elem))
	elif elem == 0:
		diff_to_non_square.append(2)
	else:
		diff_to_non_square.append(1)
if len(diff_to_square) <= n // 2:
	diff_to_non_square.sort()
	s = 0
	for i in range(len(diff_to_non_square) - n // 2):
		s += diff_to_non_square[i]
	print(s)
else:
	diff_to_square.sort()
	s = 0
	for i in range(len(diff_to_square) - n // 2):
		s += diff_to_square[i]
	print(s)


import math
n = int(input())
a = list(map(int, input().split()))
a.sort()
st = []
cnt1 = cnt2 = cnt3 = 0
for x in a:
	tmp = int(math.sqrt(x))
	if x == 0:
		cnt3 += 1
	if tmp * tmp == x:
		cnt1 += 1
	else:
		st.append(x)
		cnt2 += 1
ans = 0
if cnt1 > cnt2:
	cnt1 -= cnt3
	if cnt1 >= n / 2 - cnt2:
		print(int(n / 2 - cnt2))
	else:
		print(int(cnt1 + 2 * (n / 2 - cnt2 - cnt1)))
elif cnt1 < cnt2:
	vs = []
	for x in st:
		tmp = int(math.sqrt(x))
		MIN = min(x - tmp * tmp, (tmp + 1) * (tmp + 1) - x)
		vs.append(MIN)
	vs.sort()
	for i in range(int((cnt2 - cnt1) / 2)):
		ans += vs[i]
	print(ans)
else:
	print('0')


from math import sqrt, floor
n = int(input())
flsq = lambda x: floor(sqrt(x))
clsd = lambda f, x: min(x - f ** 2, (f + 1) ** 2 - x)
a = sorted(list(map(lambda s: (clsd(flsq(int(s)), int(s)), int(s)), input().split())))
print(sum((x[0] for x in a[:n // 2])) + sum(((1 if a[j][1] != 0 else 2) if a[j][0] == 0 else 0 for j in range(n // 2, n))))


import math

def get_min(n):
	root = math.sqrt(n)
	roott = abs(root - int(root))
	if roott >= 0.5:
		square = math.ceil(root)
	else:
		square = math.floor(root)
	return square ** 2
n = int(input())
square = []
notsquare = []
piles = [int(x) for x in input().split()]
for p in piles:
	m = get_min(p)
	if p == get_min(p):
		square += [p]
	else:
		notsquare += [abs(p - m)]
dif = n // 2 - len(square)
price = 0
if dif > 0:
	notsquare.sort()
	price += sum(notsquare[:dif])
if dif < 0:
	dif = -dif
	lst = sorted(square, reverse=True)
	for d in range(dif):
		if lst[d] == 0:
			price += 2
		else:
			price += 1
print(price)


import bisect

def is_sqr(x):
	tmp = int(x ** 0.5 + 1e-05)
	if x == tmp ** 2:
		return True
	else:
		return False

def main():
	sqlst = [i * i for i in range(32000)]
	input()
	v = list(map(int, input().split()))
	sq = nsq = 0
	for i in v:
		if is_sqr(i):
			sq += 1
		else:
			nsq += 1
	if sq == nsq:
		print(0)
	elif sq > nsq:
		magic = []
		for i in v:
			if is_sqr(i):
				if i == 0:
					magic.append(2)
				else:
					magic.append(1)
		magic.sort()
		print(sum(magic[:(sq - nsq) // 2]))
	else:
		magic = []
		for i in v:
			if not is_sqr(i):
				pos = bisect.bisect_left(sqlst, i)
				Min = min(abs(sqlst[pos] - i), abs(sqlst[pos + 1] - i), abs(sqlst[pos + 2] - i))
				if pos - 1 >= 0:
					Min = min(Min, abs(sqlst[pos - 1] - i))
				magic.append(Min)
		magic.sort()
		print(sum(magic[:(nsq - sq) // 2]))
main()


import math
n = int(input())
(a, b) = ([], [])
for x in map(int, input().split()):
	y = int(math.sqrt(x))
	mn = x - y * y
	y += 1
	mn = min(mn, y * y - x)
	a.append(mn)
	y -= 1
	b.append((x == y * y) + (not x))
for i in range(n):
	b[i] -= a[i]
print(sum(a + sorted(b)[:n // 2]))


from sys import stdin, stdout
from math import sqrt

def is_square(a):
	x = round(sqrt(a))
	return x * x == a

def need(a):
	x = int(sqrt(a))
	d1 = abs(a - x * x)
	d2 = abs(a - (x + 1) * (x + 1))
	return min(d1, d2)
n = int(input())
a = list(map(int, stdin.readline().split()))
sq_cnt = 0
for x in a:
	if is_square(x):
		sq_cnt += 1
if sq_cnt > n // 2:
	cnt0 = a.count(0)
	cnt1 = sq_cnt - cnt0
	d = sq_cnt - n // 2
	n1 = min(cnt1, d)
	n2 = d - n1
	ans = n1 + n2 * 2
	print(ans)
else:
	oper = []
	for x in a:
		oper.append(need(x))
	oper.sort()
	ans = 0
	for i in range(n // 2):
		ans += oper[i]
	print(ans)


import math
n = int(input())
arr = list(map(int, input().split()))
checks = []
zc = 0
for i in arr:
	x = i ** 0.5
	if int(x) * int(x) == i:
		checks.append(0)
		if not i:
			zc += 1
	else:
		l = math.ceil(x)
		m = math.floor(x)
		checks.append(min(abs(l * l - i), abs(i - m * m)))
checks.sort()
marks = n // 2
if checks.count(0) == marks:
	print(0)
elif checks.count(0) < marks:
	l = checks.count(0)
	s = 0
	while l < marks:
		s += checks[l]
		l += 1
	print(s)
else:
	l = checks.count(0)
	non_zero_sq = l - zc
	non_sq = n - l
	ans = 0
	marks -= non_sq
	while non_zero_sq > 0 and marks > 0:
		marks -= 1
		non_zero_sq -= 1
		ans += 1
	while marks > 0 and zc > 0:
		zc -= 1
		marks -= 1
		ans += 2
	print(ans)


n = int(input())
t = []
l = []
d = 0
c = 0
j = 0
s = 0
w = 0
sum = 0

def rtu(f):
	if int(f ** 0.5) == f ** 0.5:
		return 1
	else:
		return 0
t = input()
t = list(map(int, t.split(' ')))
for k in range(0, n):
	if t[k] == 0:
		w = w + 1
	r = t[k] ** 0.5
	if rtu(t[k]) == 1:
		c = c + 1
	s = t[k] - int(r) ** 2
	d = (int(r) + 1) ** 2 - t[k]
	if s > d:
		l.append(d)
	else:
		l.append(s)
l.sort()
for i in range(0, n // 2):
	sum = sum + l[i]
if c > n // 2 and w <= n // 2:
	sum = sum + c - n // 2
if c > n // 2 and w > n // 2:
	sum = sum + (w - n // 2) * 2 + c - w
print(sum)


from math import sqrt
n = int(input())
sz = n // 2
bins = [int(i) for i in input().split()]
sqr = 0
zeros = 0
for cnt in bins:
	if sqrt(cnt).is_integer():
		sqr += 1
	if cnt == 0:
		zeros += 1
if sqr >= sz:
	left = sqr - sz
	nonzeros = sqr - zeros
	first = max(0, left - nonzeros)
	print(left + first)
else:
	add = [0] * (n - sqr)
	i = 0
	for cnt in bins:
		root = sqrt(cnt)
		if not root.is_integer():
			lower = int(root) ** 2
			upper = (int(root) + 1) ** 2
			add[i] = min(cnt - lower, upper - cnt)
			i += 1
	add.sort()
	print(sum(add[:sz - sqr]))


n = int(input())
candies = list(map(int, input().strip().split()))

def intkoren(n):
	k = int(n ** 0.5)
	while (k + 1) * (k + 1) <= n:
		k += 1
	while k * k > n:
		k -= 1
	return k
cnt1 = 0
cnt2 = 0
new = []
for e in candies:
	u = intkoren(e)
	if e == 0:
		new.append((2, 1))
		cnt1 += 1
	elif u * u == e:
		new.append((1, 1))
		cnt1 += 1
	else:
		mini = min(e - u * u, (u + 1) * (u + 1) - e)
		new.append((mini, -1))
		cnt2 += 1
new.sort()
count = 0
if cnt1 >= cnt2:
	todo = (cnt1 - cnt2) // 2
	for (steps, v) in new:
		if todo == 0:
			break
		if v == 1:
			count += steps
			todo -= 1
else:
	todo = (cnt2 - cnt1) // 2
	for (steps, v) in new:
		if todo == 0:
			break
		if v == -1:
			count += steps
			todo -= 1
print(count)


import math

def my_dist(n):
	low = math.floor(math.sqrt(n))
	high = math.ceil(math.sqrt(n))
	return int(min(n - low * low, high * high - n))

def sol(n, my_list):
	my_list = sorted(my_list, key=lambda x: x[1])
	square_count_zero = 0
	square_count = 0
	total = 0
	for i in range(n):
		if my_list[i][0] == 0:
			square_count_zero += 1
		if my_list[i][1] == 0:
			square_count += 1
		else:
			break
	if square_count == n // 2:
		return 0
	if square_count < n // 2:
		for i in range(square_count, n // 2):
			total += my_list[i][1]
		return total
	if square_count > n // 2:
		square_pos = square_count - square_count_zero
		if square_pos >= square_count - n // 2:
			return square_count - n // 2
		else:
			total = square_count + square_count_zero - n
			return total
n = int(input())
my_list = [[int(x), my_dist(int(x))] for x in input().strip().split()]
print(sol(n, my_list))


from math import *
n = int(input())
b = list(map(int, input().split(' ')))
maxim = max(b)
squad = []
for i in range(0, int(sqrt(maxim)) + 1):
	squad.append(i ** 2)
to_quad = 0
quad_list = []
not_quad = 0
not_quad_list = []
for i in range(0, len(b)):
	if sqrt(b[i]) == int(sqrt(b[i])):
		to_quad += 1
		quad_list.append(b[i])
	else:
		not_quad += 1
		not_quad_list.append(b[i])
if to_quad == not_quad:
	print(0)
elif to_quad > not_quad:
	t = []
	answer = 0
	c = to_quad - int(n / 2)
	for i in range(0, len(quad_list)):
		if quad_list[i] == 0:
			t.append(2)
		else:
			t.append(1)
	t = sorted(t)
	for i in range(0, c):
		answer += t[i]
	print(answer)
else:
	c = not_quad - int(n / 2)
	t = []
	answer = 0
	for i in range(0, len(not_quad_list)):
		tmp = int(sqrt(not_quad_list[i]))
		r = (tmp + 1) ** 2
		l = (tmp - 1) ** 2
		t.append(min(abs(not_quad_list[i] - r), min(abs(not_quad_list[i] - tmp ** 2), abs(not_quad_list[i] - l))))
	t = sorted(t)
	for i in range(0, c):
		answer += t[i]
	print(answer)


import math
[n] = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
sqr_list_dist = []
non_sqr_dist = []
for i in a:
	if i ** 0.5 % 1 == 0:
		if i == 0:
			sqr_list_dist.append(2)
		else:
			sqr_list_dist.append(1)
	else:
		lower = math.floor(i ** 0.5) ** 2
		upper = math.ceil(i ** 0.5) ** 2
		non_sqr_dist.append(min(i - lower, upper - i))
diff = len(sqr_list_dist) - n // 2
if diff == 0:
	print(0)
elif diff > 0:
	sqr_list_dist.sort()
	print(sum(sqr_list_dist[:diff]))
else:
	non_sqr_dist.sort()
	print(sum(non_sqr_dist[:abs(diff)]))


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
from math import gcd
import io
import os
from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def digits(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def ceil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def mapin():
	return map(int, input().split())
n = int(input())
l = [float(x) for x in input().split()]
a = []
b = []
for i in range(n):
	sr = float(math.sqrt(l[i]))
	if sr.is_integer():
		a.append(int(l[i]))
	else:
		b.append(int(l[i]))
ans = 0
if len(a) < len(b):
	kk = []
	for i in range(len(b)):
		temp = b[i]
		sr = float(math.sqrt(b[i]))
		bb = math.ceil(sr)
		bb = bb ** 2
		bb = bb - temp
		aa = int(sr)
		aa **= 2
		aa = temp - aa
		kk.append(min(aa, bb))
	kk.sort()
	for i in range(0, (len(b) - len(a)) // 2):
		ans += kk[i]
	print(ans)
elif len(a) > len(b):
	a.sort(reverse=True)
	ans = 0
	for i in range((len(a) - len(b)) // 2):
		ans += 1
		if a[i] == 0:
			ans += 1
	print(ans)
else:
	print(0)


def main():
	R = lambda t: tuple(map(t, input().split()))
	rn = lambda : R(int)
	n = rn()[0]

	def cnt(v):
		sq = int(v ** (1 / 2))
		return min(v - sq ** 2, (sq + 1) ** 2 - v)
	l = sorted(((cnt(v), v) for v in rn()))
	ans = 0
	for i in range(n // 2):
		ans += l[i][0]
	for i in range(n // 2, n):
		if l[i][1] == 0:
			ans += 2
		elif l[i][1] == 1:
			ans += 1
		elif l[i][0] == 0:
			ans += 1
	print(ans)
main()


n = int(input())
L = list(map(int, input().split()))

def getkey(item):
	return item[1]

def getKey(item):
	return item[0]

def finds(n):
	rac = n ** (1 / 2)
	rac = int(rac)
	p = rac ** 2
	q = (rac + 1) ** 2
	return min(abs(n - q), abs(n - p))
D = []
for i in range(len(L)):
	D.append((L[i], finds(L[i])))
D = sorted(D, key=getkey)
sum = 0
count = 0
for i in range(len(D)):
	if D[i][1] == 0:
		count = count + 1
if count < n // 2:
	for j in range(count, n // 2):
		sum = sum + D[j][1]
elif count > n // 2:
	A = D[0:count]
	A = sorted(A, key=getKey, reverse=True)
	for i in range(count - n // 2):
		if A[i][0] == 0:
			sum = sum + 2
		else:
			sum = sum + 1
print(sum)


import math
n = int(input())
s = input()
arr = [int(x) for x in s.split()]
dp = []
b = 0
ans = 0
for i in arr:
	a = math.sqrt(i)
	a = math.floor(a)
	if a * a == i:
		b += 1
if b == n / 2:
	print(0)
elif b > n / 2:
	ans = 0
	for i in arr:
		if i == 0:
			continue
		a = math.sqrt(i)
		a = math.floor(a)
		if a * a == i and b > n / 2:
			ans += 1
			b -= 1
	if b == n / 2:
		print(ans)
	else:
		for i in arr:
			if i == 0 and b > n / 2:
				ans += 2
				b -= 1
		print(ans)
elif b < n / 2:
	for i in arr:
		a = math.sqrt(i)
		a = math.floor(a)
		if a * a != i:
			c = math.floor(a)
			d = c + 1
			k = min(i - c * c, d * d - i)
			dp.append(k)
	dp.sort()
	ans = 0
	for i in range(len(dp)):
		if b == n / 2:
			break
		else:
			ans += dp[i]
			b += 1
	print(ans)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
from heapq import *
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
n = inp()
l = li()
(a, b) = ([], [])
(x, y) = (0, 0)
l.sort(reverse=True)
for i in l:
	c = floor(pow(i, 0.5))
	while c * c < i:
		c += 1
	while c * c > i:
		c -= 1
	if c * c == i:
		a.append(i)
		x += 1
	else:
		b.append(i)
		y += 1
if x == y:
	pr(0)
elif x > y:
	ans = 0
	for i in range((x - y) // 2):
		if a[i] == 0:
			ans += 2
		else:
			ans += 1
	pr(ans)
else:
	visited = set()
	heap = []
	ans = 0
	for i in b:
		c = pow(i, 0.5)
		(cf, cc) = (floor(c), ceil(c))
		heap.append(min(abs(cc * cc - i), abs(cf * cf - i)))
	heap.sort()
	pr(sum(heap[:(y - x) // 2]))


from math import sqrt
n = int(input())
a = [int(i) for i in input().split()]
s = [0 for i in range(n)]
zero = 0
diff = []
cs = 0
cn = 0
for i in range(n):
	x = a[i]
	r = int(sqrt(x))
	if r ** 2 == x:
		cs += 1
		s[i] = 1
		if x == 0:
			zero += 1
	else:
		cn += 1
		diff.append(min(x - r ** 2, (r + 1) ** 2 - x))
delta = int((cs - cn) / 2)
if delta == 0:
	print(0)
elif delta > 0:
	if delta <= cs - zero:
		print(delta)
	else:
		print(cs - zero + (delta - (cs - zero)) * 2)
else:
	delta = -delta
	diff = sorted(diff)
	print(sum(diff[:delta]))


n = int(input())
a = list(map(int, input().split()))
x = []
for i in a:
	s = i ** 0.5
	s = round(s)
	x.append((abs(s ** 2 - i), i))
x.sort()
n2 = n // 2
ans = 0
for i in range(n2):
	ans += x[i][0]
for i in range(n2, n):
	if x[i][0] == 0:
		if x[i][1] == 0:
			ans += 2
		else:
			ans += 1
print(ans)


import math

def closest(n):
	f = math.pow(math.floor(math.sqrt(n)), 2)
	c = math.pow(math.ceil(math.sqrt(n)), 2)
	return [int(f), int(c)]
n = int(input())
piles = [int(x) for x in input().split()]
squares = []
notsquares = []
for p in range(len(piles)):
	if piles[p] == 0:
		(f, c) = [0, 1]
	else:
		(f, c) = closest(piles[p])
	if piles[p] in [f, c]:
		squares.append(piles[p])
	else:
		notsquares.append([piles[p], f, c])
price = 0
dif = len(squares) - n // 2
if dif == 0:
	print(0)
	exit()
if dif < 0:
	count = -dif
	np = []
	for p in notsquares:
		np += [min(abs(p[0] - p[1]), abs(p[2] - p[0]))]
	np.sort()
	price += sum(np[:count])
if dif > 0:
	np = sorted(squares, reverse=True)
	for i in range(dif):
		if np[i] == 0:
			price += 2
		else:
			price += 1
print(price)


n = int(input())
A = list(map(int, input().split()))
ns = 0
s = 0
N = []
S = []
for i in range(n):
	if A[i] ** 0.5 != int(A[i] ** 0.5):
		ns += 1
		N.append(A[i])
	else:
		S.append(A[i])
s = n - ns
if ns < n // 2:
	a = n // 2 - ns
	for i in range(len(S)):
		if S[i] == 0:
			S[i] = 2
		else:
			S[i] = 1
	S.sort()
	ans = 0
	for i in range(a):
		ans += S[i]
	print(ans)
else:
	a = n // 2 - s
	for i in range(ns):
		c = int(N[i] ** 0.5)
		b = c ** 2
		d = (c + 1) ** 2
		if N[i] - b <= d - N[i]:
			N[i] = N[i] - b
		else:
			N[i] = d - N[i]
	N.sort()
	ans = 0
	for i in range(a):
		ans += N[i]
	print(ans)


from math import *

def lInt(d=None):
	return map(int, input().split(d))
(n, *_) = lInt()
a = list(lInt())
is_sq = [0] * n
sq = 0
ans = 0
pos = []

def closest(v):
	w = sqrt(v)
	f = floor(w)
	c = f + 1
	fsq = f * f
	csq = c * c
	fd = v - fsq
	cd = csq - v
	return min(fd, cd)

def isS(v):
	w = int(sqrt(v))
	return w * w == v
for (i, v) in enumerate(a):
	w = int(sqrt(v))
	if w * w == v:
		is_sq[i] = 1
		sq += 1
if sq > n // 2:
	for (i, v) in enumerate(a):
		if is_sq[i] and sq > n // 2:
			if a[i]:
				ans += 1
				sq -= 1
				is_sq[i] = 0
	for (i, v) in enumerate(a):
		if is_sq[i] and sq > n // 2:
			ans += 2
			sq -= 1
elif sq < n // 2:
	for (i, v) in enumerate(a):
		if not is_sq[i]:
			pos.append(closest(a[i]))
	pos.sort()
	for j in range(n // 2 - sq):
		ans += pos[j]
else:
	ans = 0
print(ans)


def main():
	from math import sqrt
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	ps = 0
	ans = 0
	for i in a:
		k = int(sqrt(i))
		m = min(i - k * k, (k + 1) * (k + 1) - i)
		if m == 0:
			ps += 1
		b.append(m)
	if ps > n // 2:
		b.clear()
		for i in a:
			k = int(sqrt(i))
			if k * k == i:
				b.append(i)
		b.sort(reverse=True)
		for i in b:
			if i == 0:
				ans += 2
			else:
				ans += 1
			ps -= 1
			if ps <= n // 2:
				break
		print(ans)
		return
	b.sort()
	for i in range(n // 2):
		ans += b[i]
	print(ans)
	return
main()


import math
n = int(input())
nums = [int(i) for i in input().split()]
diff = []
counter = 0
zeros = 0
for i in range(0, n):
	if nums[i] == 0:
		zeros += 1
	x = nums[i] ** 0.5
	y = math.floor(x)
	if y * y == nums[i]:
		diff.append(0)
		counter += 1
	else:
		z = (y + 1) * (y + 1)
		y = y * y
		a = min(nums[i] - y, z - nums[i])
		diff.append(a)
if counter == n / 2:
	print(0)
elif counter < n / 2:
	result = 0
	diff.sort()
	test = 0
	des = n / 2 - counter
	for a in range(0, n):
		if diff[a] == 0:
			continue
		elif test < des:
			test += 1
			result += diff[a]
		else:
			break
	print(int(result))
else:
	result = 0
	nonzeros = counter - zeros
	x = counter - n / 2
	if x <= nonzeros:
		print(int(counter - n / 2))
	else:
		result = nonzeros + (x - nonzeros) * 2
		print(int(result))


from math import sqrt
n = int(input())
arr = [int(i) for i in input().split()]
greedy = [(min(arr[i] - int(sqrt(arr[i])) * int(sqrt(arr[i])), (int(sqrt(arr[i])) + 1) * (int(sqrt(arr[i])) + 1) - arr[i]), arr[i]) for i in range(len(arr))]
count = 0
ans = 0
greedy.sort()
for (i, j) in greedy:
	if count < n / 2:
		ans += i
	elif j == 0:
		ans += 2
	elif i == 0:
		ans += 1
	count += 1
print(ans)


import sys
input = sys.stdin.buffer.readline
import os
from math import *
n = int(input())
arr = list(map(int, input().split()))
sq_count = 0
move = []
zero = 0
for i in range(n):
	if arr[i] == 0:
		zero += 1
	c = sqrt(arr[i])
	if int(c) * int(c) == arr[i]:
		sq_count += 1
	else:
		c = round(c)
		move.append(int(fabs(c * c - arr[i])))
notsq = n - sq_count
if sq_count == notsq:
	print('0')
elif sq_count > notsq:
	rest = n // 2 - notsq
	if zero <= n // 2:
		print(rest)
	else:
		con = zero - n // 2
		print(con * 2 + (rest - con))
else:
	con = n // 2 - sq_count
	move.sort()
	print(sum(move[0:con]))


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
cnt1 = 0
cnt2 = 0
ok = []
ng = []
for i in range(n):
	b = a[i]
	if int(b ** 0.5) ** 2 == b:
		cnt1 += 1
		if b == 0:
			ok.append(2)
		else:
			ok.append(1)
	else:
		cnt2 += 1
		c1 = int(b ** 0.5) ** 2
		c2 = (int(b ** 0.5) + 1) ** 2
		ng.append(min(abs(b - c1), abs(b - c2)))
ok.sort()
ng.sort()
if cnt1 == cnt2:
	print(0)
elif cnt1 > cnt2:
	res = (cnt1 - cnt2) // 2
	print(sum(ok[:res]))
else:
	res = (cnt2 - cnt1) // 2
	print(sum(ng[:res]))


n = int(input())
a = list(map(int, input().split()))
cnt = [0] * n
cc = [0] * n
for i in range(n):
	c = int(a[i] ** 0.5)
	d = min(a[i] - c * c, (c + 1) ** 2 - a[i])
	cnt[i] = [d, a[i]]
	cc[i] = d
cnt.sort()
cc.sort()
print(sum(cc[0:n // 2]) + cnt[n // 2:].count([0, 0]) + cc[n // 2:].count(0))


from math import sqrt, floor, ceil

def isSquare(n):
	x = sqrt(n)
	if x % 1 == 0:
		return True
	else:
		return False
n = int(input())
arr = [int(x) for x in input().split()]
Is = 0
Take = []
Square = []
for i in arr:
	if isSquare(i):
		Square.append(i)
		Is += 1
	else:
		niche = floor(sqrt(i))
		upar = ceil(sqrt(i))
		Take.append(min(abs(i - niche ** 2), abs(upar ** 2 - i)))
if Is >= n / 2:
	Square.sort(reverse=True)
	ans = 0
	for i in range(Is - (n >> 1)):
		if Square[i]:
			ans += 1
		else:
			ans += 2
	print(ans)
else:
	Take.sort()
	ans = 0
	for i in range((n >> 1) - Is):
		ans += Take[i]
	print(ans)


from math import sqrt

def main():
	n = int(input())
	piles = [int(x) for x in input().split()]
	spiles = sorted(piles)
	nearest = []
	cost = []
	for a in piles:
		tmp = int(sqrt(a))
		lower = tmp ** 2
		upper = (tmp + 1) ** 2
		if a - lower <= upper - a:
			nearest.append(lower)
		else:
			nearest.append(upper)
		cost.append(abs(a - nearest[-1]))
	cost = sorted(cost)
	summ = 0
	for i in range(int(n / 2)):
		summ += cost[i]
	for j in range(int(n / 2), n):
		if cost[j] == 0:
			summ += 1
			if spiles[j] == 0:
				summ += 1
		else:
			break
	print(summ)
main()


n = int(input())
l = list(map(int, input().split()))
ll = []
l.sort()
for i in range(n):
	ll.append([min(l[i] - int(l[i] ** 0.5) ** 2, (int(l[i] ** 0.5) + 1) ** 2 - l[i]), i])
ll.sort()
ans = 0
if ll[n // 2][0] == 0:
	i = n // 2
	while ll[i][0] == 0:
		if l[ll[i][1]] == 0:
			ans += 2
		else:
			ans += 1
		i += 1
		if i == n:
			break
for i in range(n // 2):
	ans += ll[i][0]
print(ans)


def isPerfect(n):
	s = int(n ** 0.5)
	if n == s ** 2:
		return True
	else:
		return False

def PerfectUp(n):
	s = int(n ** 0.5)
	return (s + 1) ** 2

def PerfectDown(n):
	s = int(n ** 0.5)
	return s ** 2
n = int(input())
l = input().split()
p = []
np = []
for i in range(0, len(l)):
	l[i] = int(l[i])
	if isPerfect(l[i]):
		p.append(l[i])
	else:
		np.append(l[i])
if len(p) == int(n / 2):
	print(0)
elif len(p) < int(n / 2):
	cost = []
	for i in range(len(np)):
		u = PerfectUp(np[i])
		d = PerfectDown(np[i])
		cost.append(min(abs(np[i] - u), abs(np[i] - d)))
	cost = sorted(cost)
	Sum = 0
	for i in range(int(n / 2) - len(p)):
		Sum = Sum + cost[i]
	print(Sum)
else:
	ZeroCount = 0
	for i in p:
		if i == 0:
			ZeroCount = ZeroCount + 1
	need = len(p) - int(n / 2)
	Sum = 0
	if len(p) - ZeroCount < need:
		Sum = Sum + len(p) - ZeroCount
		need = need - (len(p) - ZeroCount)
		Sum = Sum + 2 * need
		print(Sum)
	else:
		Sum = Sum + need
		print(Sum)


import math
n = int(input())
arr = list(map(int, input().split()))
e = 0
o = 0
cnt = []
d = []
for i in range(n):
	var = int(math.sqrt(arr[i]))
	if var ** 2 == arr[i] or (var + 1) ** 2 == arr[i]:
		e += 1
	else:
		o += 1
		d.append(arr[i])
		cnt.append(min(abs(var ** 2 - arr[i]), abs((var + 1) ** 2 - arr[i])))
if o == e == n // 2:
	print(0)
elif o < e:
	var = n // 2 - o
	ans = 0
	ls = sorted(arr)
	for j in range(n - 1, -1, -1):
		if ls[j] in d:
			continue
		if ls[j] >= 1:
			ans += 1
			var -= 1
		elif ls[j] == 0:
			ans += 2
			var -= 1
		if var == 0:
			print(ans)
			break
elif o > e:
	var = n // 2 - e
	cnt.sort()
	ans = sum(cnt[:var])
	print(ans)


import math
n = int(input())
l = list(map(int, input().split()))
zero = l.count(0)
for i in range(n):
	r = round(math.sqrt(l[i]))
	l[i] = abs(l[i] - r * r)
l.sort()
rzero = max(0, zero - n // 2)
print(sum(l[0:n // 2]) + rzero * 2 + l[n // 2:n].count(0) - rzero)


from sys import stdin, stdout
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import *
input = stdin.readline
prin = stdout.write
from random import sample
from collections import Counter, deque
from math import sqrt, ceil, log2, gcd
mod = 10 ** 9 + 7

class DisjSet:

	def __init__(self, n):
		self.rank = [1] * n
		self.parent = [i for i in range(n)]

	def find(self, x):
		if self.parent[x] != x:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, x, y):
		xset = self.find(x)
		yset = self.find(y)
		if xset == yset:
			return
		if self.rank[xset] < self.rank[yset]:
			self.parent[xset] = yset
		elif self.rank[xset] > self.rank[yset]:
			self.parent[yset] = xset
		else:
			self.parent[yset] = xset
			self.rank[xset] = self.rank[xset] + 1

def f(arr, i, j, d, dist):
	if i == j:
		return
	nn = max(arr[i:j])
	for tl in range(i, j):
		if arr[tl] == nn:
			dist[tl] = d
			f(arr, i, tl, d + 1, dist)
			f(arr, tl + 1, j, d + 1, dist)

def ps(n):
	cp = 0
	lk = 0
	arr = {}
	while n % 2 == 0:
		n = n // 2
		lk += 1
	arr[2] = lk
	for ps in range(3, ceil(sqrt(n)) + 1, 2):
		lk = 0
		while n % ps == 0:
			n = n // ps
			arr.append(n)
			arr.append(ps ** (lk + 1))
			lk += 1
		arr[ps] = lk
	if n != 1:
		lk += 1
		arr[n] = lk
	return arr

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def factorials(n, r):
	slr = n
	dpr = r
	qlr = 1
	qs = 1
	mod = 10 ** 9 + 7
	for ip in range(n - r + 1, n + 1):
		qlr = qlr * ip % mod
	for ij in range(1, r + 1):
		qs = qs * ij % mod
	ans = qlr * modInverse(qs) % mod
	return ans

def modInverse(b):
	qr = 10 ** 9 + 7
	return pow(b, qr - 2, qr)
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def power(arr):
	listrep = arr
	subsets = []
	for i in range(2 ** len(listrep)):
		subset = []
		for k in range(len(listrep)):
			if i & 1 << k:
				subset.append(listrep[k])
		subsets.append(subset)
	return subsets

def dis(xa, ya, xb, yb):
	return sqrt((xa - xb) ** 2 + (ya - yb) ** 2)

def ii():
	return int(input())

def ilist():
	return [int(x) for x in input().strip().split()]

def outstrlist(array: list) -> str:
	array = [str(x) for x in array]
	return ' '.join(array)

def islist():
	return list(map(str, input().split().rstrip()))

def outfast(arr: list) -> str:
	ss = ''
	for ip in arr:
		ss += str(ip) + ' '
	return prin(ss)

def pda(n):
	list = []
	for i in range(1, int(sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				list.append(i)
			else:
				list.append(int(n / i))
				list.append(i)
	return list
t = 1
for jj in range(t):
	n = ii()
	arr = ilist()
	crr = []
	i = 0
	while i * i <= 10 ** 9 * 2:
		crr.append(i * i)
		i += 1
	jj = set(crr)
	sq = 0
	nsq = 0
	drr = []
	for i in range(n):
		if arr[i] in jj:
			sq += 1
		else:
			nsq += 1
			kk = bl(crr, arr[i], 0, len(crr))
			drr.append(min(crr[kk] - arr[i], arr[i] - crr[kk - 1]))
	if sq >= nsq:
		alp = arr.count(0)
		if alp <= n // 2:
			print(sq - n // 2)
		else:
			count0 = alp - n // 2 - (sq - alp)
			print(count0 * 2 + (sq - alp) * 1)
	else:
		al = nsq - n // 2
		drr.sort()
		print(sum(drr[:al]))


from sys import stdin, stdout
n = int(stdin.readline().rstrip())
a = list(map(int, stdin.readline().rstrip().split()))
a.sort()
squareList = [i * i for i in range(int(1000000000 ** 0.5) + 2)]
squareCount = 0
zeroCount = 0
lowerSquare = -1
upperSquare = 0
index = 0
distanceList = []
for x in a:
	while x > upperSquare:
		index += 1
		upperSquare = squareList[index]
		lowerSquare = squareList[index - 1]
	if x == upperSquare:
		squareCount += 1
		if x == 0:
			zeroCount += 1
	else:
		distanceList.append(min([upperSquare - x, x - lowerSquare]))
distanceList.sort()
change = 0
if squareCount > n // 2:
	nonZeroCount = squareCount - zeroCount
	if squareCount - n // 2 <= nonZeroCount:
		change = squareCount - n // 2
	else:
		change = nonZeroCount + 2 * (squareCount - n // 2 - nonZeroCount)
elif squareCount < n // 2:
	change = sum(distanceList[:n // 2 - squareCount])
print(change)


from math import sqrt

def check(x):
	sq = int(sqrt(x))
	while sq * sq < x:
		sq += 1
	return (sq * sq == x, sq)
n = int(input())
a = map(int, input().split())
(sq, non_sq) = (0, 0)
(sqs, non_sqs) = ([], [])
for _ in a:
	(res, root) = check(_)
	sq += res
	non_sq += 1 - res
	if res:
		sqs.append(2 - bool(_))
	else:
		non_sqs.append(min(_ - (root - 1) ** 2, root ** 2 - _))
sqs.sort()
non_sqs.sort()
ans = 0
if sq > non_sq:
	for i in range(sq - non_sq >> 1):
		ans += sqs[i]
elif sq < non_sq:
	for i in range(non_sq - sq >> 1):
		ans += non_sqs[i]
else:
	pass
print(ans)


n = int(input())
s = 0
kolzero = 0
l = [int(i) for i in input().split()]
kv = 0
for i in range(n):
	if int(l[i] ** 0.5) ** 2 == l[i]:
		kv += 1
g = [0] * n
for i in range(n):
	if l[i] == 0:
		kolzero += 1
	a = int(l[i] ** 0.5)
	b = a + 1
	a = a ** 2
	b = b ** 2
	if l[i] - a < b - l[i]:
		g[i] = l[i] - a
	else:
		g[i] = b - l[i]
i = 0
x = 0
if kv >= n // 2:
	s = kv - n // 2
	if kolzero > n // 2:
		s += kolzero - n // 2
	print(s)
else:
	g.sort()
	while x < n // 2 - kv:
		if g[i] != 0:
			s += g[i]
			x += 1
		i += 1
	print(s)


n = int(input())
a = list(map(int, input().split()))

def isqrt(n):
	x = n
	y = (x + 1) // 2
	while y < x:
		x = y
		y = (x + n // x) // 2
	return x
cnt = [0] * n
p = 0
q = 0
sqrtCount = 0
ans = 0
for i in range(n):
	x = isqrt(a[i])
	if a[i] == x * x:
		sqrtCount += 1
		if a[i] == 0:
			p += 1
		else:
			q += 1
	cnt[i] = min(a[i] - x * x, (x + 1) * (x + 1) - a[i])
if sqrtCount >= n / 2:
	num = n // 2
	f = min(p, num)
	p -= f
	num -= f
	ans = p * 2 + (q - num) * 1
	print(ans)
else:
	cnt.sort()
	ans = 0
	for i in range(n // 2):
		ans += cnt[i]
	print(ans)


from sys import stdin, stdout
sze = 10 ** 5
power = []
for i in range(sze):
	power.append(i * i)

def sqrt(v):
	(l, r) = (0, sze)
	while r - l > 1:
		m = l + r >> 1
		if power[m] <= v:
			l = m
		else:
			r = m
	return l

def add_f(v):
	if not v:
		first.append(2)
	else:
		first.append(1)

def add_s(v):
	(l, r) = (0, sze)
	while r - l > 1:
		m = l + r >> 1
		if power[m] <= v:
			l = m
		else:
			r = m
	second.append(min(v - power[l], power[r] - v))
n = int(stdin.readline())
values = list(map(int, stdin.readline().split()))
(first, second) = ([], [])
for v in values:
	a = sqrt(v)
	if a * a == v:
		add_f(v)
	else:
		add_s(v)
first.sort()
second.sort()
ans = 0
k = n // 2
if len(first) < len(second):
	for i in range(k - len(first)):
		ans += second[i]
elif len(first) > len(second):
	for i in range(k - len(second)):
		ans += first[i]
stdout.write(str(ans))


import math

def check_square(n):
	return min(math.ceil(n ** 0.5) ** 2 - n, n - math.floor(n ** 0.5) ** 2)
k = int(input())
s = input()
L = s.split(' ')
L = [int(n) for n in L]
sq = []
nonsq = []
for e in L:
	if check_square(e) == 0:
		sq.append(e)
	else:
		nonsq.append((e, check_square(e)))
if len(sq) == k // 2 and len(nonsq) == k // 2:
	print(0)
elif len(sq) > len(nonsq):
	diff = k // 2 - len(nonsq)
	sq.sort(reverse=True)
	ans = 0
	for i in range(diff):
		if sq[i] != 0:
			ans += 1
		else:
			ans += 2
	print(ans)
else:
	diff = k // 2 - len(sq)
	nonsq.sort(key=lambda x: x[1])
	ans = 0
	for i in range(diff):
		ans += nonsq[i][1]
	print(ans)


import decimal
decimal.getcontext().prec = 20

def nearest(a):
	a = int(a)
	x = str(decimal.Decimal(a).sqrt()) + '.'
	x = int(x[:x.find('.')])
	return min(a - x * x, (x + 1) ** 2 - a)
n = int(input())
b = list(map(int, input().split()))
b.sort()
a = list(map(nearest, b))
a.sort()
if a[n // 2] == 0:
	count = 0
	for i in range(n // 2):
		if a[i + n // 2] == 0:
			count += 1
		else:
			break
	for i in range(n // 2):
		if b[i + n // 2] == 0:
			count += 1
		else:
			break
	print(count)
else:
	print(sum(a[:n // 2]))


def nexqd(x):
	l = 0
	r = 100000
	while r - l > 1:
		m = (l + r) // 2
		if m ** 2 > x:
			r = m
		else:
			l = m
	return min(r ** 2 - x, x - l ** 2)

def nexunqd(x):
	if 0 == x:
		return 2
	if nexqd(x) == 0:
		return 1
	return 0
n = int(input())
L = []
for i in list(map(int, input().split())):
	L.append((nexqd(i) - nexunqd(i), nexqd(i), nexunqd(i), i))
L.sort()
i = 0
ans = 0
while i < n // 2:
	if L[i][1] < 0:
		pass
	ans += L[i][1]
	i += 1
while i < n:
	if L[i][2] < 0:
		pass
	ans += L[i][2]
	i += 1
print(ans)


import math
n = int(input())
arr = list(map(int, input().split()))
dif = []
ans = 0
cntsqrt = 0
cntnon = 0
zerocnt = 0
for i in range(n):
	x = arr[i]
	if arr[i] == 0:
		zerocnt += 1
	if x ** 0.5 == int(x ** 0.5):
		dif.append(0)
		cntsqrt += 1
	else:
		upper = math.ceil(x ** 0.5)
		lower = math.floor(x ** 0.5)
		dif.append(min(upper ** 2 - x, x - lower ** 2))
		cntnon += 1
dif.sort()
i = 0
cnt = cntsqrt - zerocnt
if cntsqrt > cntnon:
	while cntsqrt > cntnon:
		if ans >= cnt:
			ans += 2
		else:
			ans += 1
		cntsqrt -= 1
		cntnon += 1
else:
	for i in range(n // 2):
		ans += dif[i]
print(ans)


import bisect
n = int(input())
lst2 = []
j = 0
x = 0
lst3 = []
lst4 = []
while j ** 2 <= 5 * 10 ** 9:
	lst2.append(j ** 2)
	j += 1
lst = [int(x) for x in input().split()]
for i in lst:
	k = bisect.bisect_left(lst2, i)
	if k == 0 or abs(lst2[k] - i) < abs(lst2[k - 1] - i):
		lst3.append(abs(lst2[k] - i))
		if abs(lst2[k] - i) == 0:
			lst4.append(i)
	else:
		lst3.append(abs(lst2[k - 1] - i))
lst3 = sorted(lst3)
lst4 = sorted(lst4)
answer = 0
if lst3.count(0) > len(lst3) // 2:
	for i in range(len(lst4) - n // 2):
		if lst4[-1 - i] == 0:
			answer += 2
		else:
			answer += 1
if lst3.count(0) < len(lst3) // 2:
	answer += sum(lst3[:n // 2])
print(answer)


n = int(input())
l = [int(i) for i in input().split()]
sq = []
no = []
for i in l:
	if int(i ** 0.5) == i ** 0.5:
		sq.append(i)
	else:
		no.append(i)
if len(sq) == n // 2:
	print(0)
	exit()
if len(sq) > n // 2:
	ab = []
	rem = len(sq) - n // 2
	for i in sq:
		if i == 0:
			ab.append(2)
		else:
			ab.append(1)
	ab.sort()
	print(sum(ab[:rem]))
else:
	from math import floor as f, ceil as c
	ab = []
	rem = n // 2 - len(sq)
	for i in no:
		lo = f(i ** 0.5)
		lo *= lo
		up = c(i ** 0.5)
		up *= up
		ab.append(min(i - lo, up - i))
	ab.sort()
	print(sum(ab[:rem]))


sqrs = [-1] + [i * i for i in range(31625)]
import sys
input = sys.stdin.readline
from bisect import bisect_left
n = int(input())
(na, nb, A, B) = (0, 0, list(), list())
for v in map(int, input().split()):
	i = bisect_left(sqrs, v)
	dist = min(v - sqrs[i - 1], sqrs[i] - v)
	if dist == 0:
		na += 1
		dist = 2 if v == 0 else 1
		A.append(dist)
	else:
		nb += 1
		B.append(dist)
ans = 0
if na > nb:
	A.sort()
	ans = sum(A[:(na - nb) // 2])
elif nb > na:
	B.sort()
	ans = sum(B[:(nb - na) // 2])
print(ans)