Gardener Alexey teaches competitive programming to high school students. To congratulate Alexey on the Teacher's Day, the students have gifted him a collection of wooden sticks, where every stick has an integer length. Now Alexey wants to grow a tree from them.

The tree looks like a polyline on the plane, consisting of all sticks. The polyline starts at the point $(0, 0)$. While constructing the polyline, Alexey will attach sticks to it one by one in arbitrary order. Each stick must be either vertical or horizontal (that is, parallel to $OX$ or $OY$ axis). It is not allowed for two consecutive sticks to be aligned simultaneously horizontally or simultaneously vertically. See the images below for clarification.

Alexey wants to make a polyline in such a way that its end is as far as possible from $(0, 0)$. Please help him to grow the tree this way.

Note that the polyline defining the form of the tree may have self-intersections and self-touches, but it can be proved that the optimal answer does not contain any self-intersections or self-touches.


-----Input-----

The first line contains an integer $n$ ($1 \le n \le 100\,000$) — the number of sticks Alexey got as a present.

The second line contains $n$ integers $a_1, \ldots, a_n$ ($1 \le a_i \le 10\,000$) — the lengths of the sticks.


-----Output-----

Print one integer — the square of the largest possible distance from $(0, 0)$ to the tree end.


-----Examples-----
Input
3
1 2 3

Output
26
Input
4
1 1 2 2

Output
20


-----Note-----

The following pictures show optimal trees for example tests. The squared distance in the first example equals $5 \cdot 5 + 1 \cdot 1 = 26$, and in the second example $4 \cdot 4 + 2 \cdot 2 = 20$.

 [Image] 

 [Image]

Difficulty: interview

Starter code:

Solutions:
n = int(input())
l = list(map(int,input().split()))
l.sort()
a = l[:n//2]
b = l[n//2:]
print(sum(a)**2+sum(b)**2)

n = int(input())
a = list(map(int, input().split()))
a.sort()
x = sum(a[:n//2])
# print(x)
print(x**2 + (sum(a) - x)**2)

N = int(input())
sticks = sorted(list(map(int, input().split())))
lo, hi = 0, N - 1

X = 0
Y = 0

step = 0
while lo <= hi:
    if step == 0:
        # horizontal
        X += sticks[hi]
        hi -= 1
    else:
        # vertical
        Y += sticks[lo]
        lo += 1
    step = 1 - step

print(X * X + Y * Y)


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

x = sum(a[:n // 2])
y = sum(a[n // 2:])

print(x ** 2 + y ** 2)


def mi():
        return list(map(int, input().split()))
'''
3
1 2 3
4
1 1 2 2
'''
n = int(input())
a = list(mi())

a.sort()
f,l = 0,0
for i in range(n//2):
    f+=a[i]
    l+=a[n-1-i]
if n%2:
    if f>l:
        f+=a[n//2]
    else:
        l+=a[n//2]
print(f**2+l**2)


n=int(input())
y=[int(x) for x in input().split()]
y.sort()
a=y[:int(n/2)]
b=y[int(n/2):]
print(sum(a)**2+sum(b)**2)


import math
from collections import deque, defaultdict
from sys import stdin, stdout
input = stdin.readline
# print = stdout.write
listin = lambda : list(map(int, input().split()))
mapin = lambda : map(int, input().split())
n = int(input())
a = listin()
a.sort()
x, y = 0, 0
a = deque(a)
for i in range(n):
    if i%2:
        y+=a.popleft()
    else:
        x+=a.pop()
print(x**2+y**2)

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

a.sort()
print(sum(a[:n//2])**2 + sum(a[n//2:])**2)


import sys
input = sys.stdin.readline

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

a = sorted(a, reverse = True)
ans1 = sum(a[0:(n+1)//2])
ans2 = sum(a[(n+1)//2:n])
print(ans1**2 + ans2**2)

n=int(input())
counter=0
a=sorted([int(x) for x in input().split()])
for i in range(n//2):
    counter+=a[i]
s=sum(a)
print((s-counter)**2+counter**2)


n = int(input())
l = list(map(int, input().split()))
l.sort()
val = n//2
x = 0
y = 0
for i in range(val):
	x+=l[i]
for i in range(val, n):
	y+=l[i]
print((x**2)+(y**2))


import sys


def main():
    n = int(input())
    a = list(map(int, sys.stdin.readline().split()))
    a.sort(reverse=True)
    x = y = 0
    i = 0
    while i < n - i - 1:
        x += a[i]
        y += a[n - i - 1]
        i += 1
    if (n % 2):
        x += a[i]
    print(x * x + y * y)

main()


from collections import deque
n = int(input())

sticks = list(map(int, input().split()))
dq = deque(sorted(sticks))

lenx=0
leny=0
while len(dq) > 0:
    lenx+=dq.pop()
    if len(dq)>0:
        leny+=dq.popleft()
print(lenx**2+leny**2)




n = int(input())
skaitli = list(map(int, input().split()))
isakais = n // 2
skaitli.sort()
isie = skaitli[0:isakais]
garie = skaitli[isakais:]
issum = sum(isie)
garsum = sum(garie)
suma =  issum * issum + garsum * garsum
print(suma)

n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
x,y=0,0
for i in range(n//2):
    x += a[i]
for i in range(n//2,n):
    y += a[i]
print(pow(x,2)+pow(y,2))

import sys
import math
import itertools
import collections

def getdict(n):
    d = {}
    if type(n) is list or type(n) is str:
        for i in n:
            if i in d:
                d[i] += 1
            else:
                d[i] = 1
    else:
        for i in range(n):
            t = ii()
            if t in d:
                d[t] += 1
            else:
                d[t] = 1
    return d
def divs(n, start=1):
    r = []
    for i in range(start, int(math.sqrt(n) + 1)):
        if (n % i == 0):
            if (n / i == i):
                r.append(i)
            else:
                r.extend([i, n // i])
    return r
def cdiv(n, k): return n // k + (n % k != 0)
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(map(int, input().split()))
def lcm(a, b): return abs(a*b) // math.gcd(a, b)
def wr(arr): return '\n'.join(map(str, arr))
def revn(n): return int(str(n)[::-1])
def prime(n):
    if n == 2: return True
    if n % 2 == 0 or n <= 1: return False
    sqr = int(math.sqrt(n)) + 1
    for d in range(3, sqr, 2):
        if n % d == 0: return False
    return True


n = ii()
a = li()
a.sort(reverse=True)
print(sum(a[:n//2 + n % 2]) ** 2 + sum(a[n//2 + n % 2:]) ** 2)

n = int(input())
a = list(map(int, input().split(" ")))
a = sorted(a)
x = 0
y = 0
for i in range(n//2):
    y += a[i]
for i in range(n//2, n):
    x += a[i]
res = x*x + y*y
print(res)

n = int(input())
a = [int(x) for x in input().split()]
a.sort()
n = len(a)
x = sum(a[:n//2])
y = sum(a[n//2:])
print(x ** 2 + y ** 2)

import sys

input = sys.stdin.readline


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


def read_is(n=1):
    return [read_i() for _ in range(n)]


n = int(input())
ls = read_i()
ls.sort()
print(sum(ls[:n // 2])**2 + sum(ls[n // 2:])**2)

'''input
4
1 1 2 2
'''
import sys
from collections import defaultdict as dd
from itertools import  permutations as pp
from itertools import combinations as cc
from collections import Counter as ccd
from random import randint as rd
from bisect import bisect_left as bl
from  heapq import heappush as hpush
from heapq import heappop as hpop
mod=10**9+7

def ri(flag=0):
	if flag==0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())


n = ri(1)
a = ri()
a.sort(reverse =True)

ans = 0

first = 0

if n%2==1:
	for i in range(n//2+1):
		first+=a[i]
else:
	for i in range(n//2):
		first +=a[i]

second = sum(a)-first

print(first**2 + second**2)


n = int(input())
a = list(map(int,input().split()))
a.sort()
s = sum(a)
h = sum(a[n//2:])
v = s-h
print(h*h+v*v)


Scount = int(input())
sticks = [int(x) for x in input().split(' ')]
sticks.sort()
horizontal = 0
for i in range(Scount - 1, Scount // 2 - 1, -1):
    horizontal += sticks[i]
vertical = 0
for i in range(Scount // 2 - 1, -1, -1):
    vertical += sticks[i]
print(horizontal ** 2 + vertical ** 2)