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: interview

Starter code:

Solutions:
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()

#print(new, cnt1,cnt2)

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)


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)
    
    


n=int(input())
arr=list(map(int,input().strip().split(' ')))
sq=0
nsq=0
sqq=[]
nsqq=[]
for i in arr:
    t=int(i**.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**.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)


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([(clsd(flsq(int(s)), int(s)), int(s)) for s in 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)))


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


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)
else:
    if(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 math import *
def lInt(d = None): return list(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)


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


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)


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())
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())
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:
        b.append(i)
    else:
        v.append(min(i - c * c, (c + 1) * (c + 1) - i))
b.sort(reverse=True)
v.sort()
for i in range(len(b) - n // 2):
    ans += 1 + (b[i] == 0)
for i in range(n // 2 - len(b)):
    ans += v[i]
print(ans)


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:
        b.append(i)
    else:
        v.append(min(i - c * c, (c + 1) * (c + 1) - i))
b.sort(reverse=True)
v.sort()
for i in range(len(b) - n // 2):
    ans += 1 + (b[i] == 0)
for i in range(n // 2 - len(b)):
    ans += v[i]
print(ans)


# -*- coding: utf-8 -*-
"""
Created on Sat Dec 16 19:33:27 2017

@author: ms
"""
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()



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)
        #print(ind)
        ap(min(i-sq[ind-1],sq[ind]-i))
a=sorted(a)
s=sum(a[:n])
#print(a,n,s)
#print(a,s)
if s==0:
    print(n-a[::-1].index(0)+max(0,nules-n))
else:
    print(s)




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)


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)
        


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)

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

def solve():
    sq=[i*i for i in range(32630)]
    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)
            #print(ind)
            ap(min(i-sq[ind-1],sq[ind]-i))
    a=sorted(a)
    s=sum(a[:n])
    #print(a,n,s)
    #print(a,s)
    if s==0:
        print(n-a[::-1].index(0)+max(0,nules-n))
    else:
        print(s)
solve()




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