Lunar New Year is approaching, and Bob is struggling with his homework – a number division problem.

There are $n$ positive integers $a_1, a_2, \ldots, a_n$ on Bob's homework paper, where $n$ is always an even number. Bob is asked to divide those numbers into groups, where each group must contain at least $2$ numbers. Suppose the numbers are divided into $m$ groups, and the sum of the numbers in the $j$-th group is $s_j$. Bob's aim is to minimize the sum of the square of $s_j$, that is $$\sum_{j = 1}^{m} s_j^2.$$

Bob is puzzled by this hard problem. Could you please help him solve it?


-----Input-----

The first line contains an even integer $n$ ($2 \leq n \leq 3 \cdot 10^5$), denoting that there are $n$ integers on Bob's homework paper.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^4$), describing the numbers you need to deal with.


-----Output-----

A single line containing one integer, denoting the minimum of the sum of the square of $s_j$, which is $$\sum_{i = j}^{m} s_j^2,$$ where $m$ is the number of groups.


-----Examples-----
Input
4
8 5 2 3

Output
164

Input
6
1 1 1 2 2 2

Output
27



-----Note-----

In the first sample, one of the optimal solutions is to divide those $4$ numbers into $2$ groups $\{2, 8\}, \{5, 3\}$. Thus the answer is $(2 + 8)^2 + (5 + 3)^2 = 164$.

In the second sample, one of the optimal solutions is to divide those $6$ numbers into $3$ groups $\{1, 2\}, \{1, 2\}, \{1, 2\}$. Thus the answer is $(1 + 2)^2 + (1 + 2)^2 + (1 + 2)^2 = 27$.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = []
a = input().split()
a = [int(i) for i in a]
a.sort()
ans = 0
for i in range(n // 2):
    ans += (a[i] + a[n - i - 1]) ** 2
print(ans)

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



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


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

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

n = ii()
a = li()
a.sort()
i, j = 0, n - 1
ans = 0
while i < j:
    ans += (a[i] + a[j]) ** 2
    i += 1
    j -= 1
print(ans)


n=int(input())
l=[int(i) for i in input().split()]
l=sorted(l)
ans=0 
for i in range(n//2):
    ans=ans+((l[i]+l[n-i-1])*(l[i]+l[n-i-1]))
print(ans)


n = int(input())
A = list(map(int, input().split()))
A.sort()
answer = 0
for i in range(n // 2):
    answer += (A[i] + A[n - i - 1]) ** 2
print(answer)

n = int(input())
s = sorted(list(map(int, input().split())))
answer = 0
for i in range(n // 2):
    answer += (s[i] + s[n - i - 1]) ** 2
print(answer)


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

n=int(input())
a=list(map(int,input().split()))
a.sort()
su=0
for i in range (n//2):
	su+=((a[i]+a[n-i-1])**2)

print(su)


'''input
6
1 1 1 2 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
import heapq
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()
ans=0
for i in range(n//2):
	ans+=(a[i]+a[n-i-1])**2
print(ans)

n = int(input())

nums = sorted(map(int, input().split()))

ans = 0
i = 0
ln = len(nums)
while i < ln // 2:
    ans += (nums[i] + nums[ln - i - 1]) ** 2
    i += 1

print(ans)


import re, math, decimal, bisect
def read(): return input().strip()
def iread(): return int(input().strip())
def viread(): return [int(_) for _ in input().strip().split()]

# code goes here
n = iread()
arr = sorted(viread())
ans = 0
for i in range(n//2):
	ans += (arr[i] + arr[-(i+1)])**2
print(ans)


# -*- coding: utf-8 -*-
# @Time    : 2019/1/31 20:42
# @Author  : LunaFire
# @Email   : gilgemesh2012@gmail.com
# @File    : C. Lunar New Year and Number Division.py


def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ret = 0
    for i in range(n // 2):
        ret += (a[i] + a[n - i - 1]) ** 2
    print(ret)


def __starting_point():
    main()

__starting_point()

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


n=int(input())
a=list(map(int,input().split()))
a.sort()
s=0
for i in range(n//2):
  s+=pow((a[i]+a[n-i-1]),2)
print(s)



m=int(input())
num=[int(x) for x in input().split()]
num.sort()
counter=0
for i in range(m//2):
    counter+=(num[i]+num[m-i-1])**2
print(counter)


""" 
Author: Raj Singh
Date:   31.01.19"""
from sys import stdin,stdout
#import math#import heapq#import operator
#from collections import OrderedDict,Counter,defaultdict
#def getKey(item):return item[0]#l=sorted(l, key=getKey,reverse=True) 
def inp():
    return stdin.readline()
def minp():
    return map(int,stdin.readline().rstrip().split())
def linp():
    return list(minp())

def main():
    n=int(inp())
    lst=linp()
    lst.sort()
    s=0
    for i in range(int(n/2)):
        s+=(lst[n-i-1]+lst[i])**2
    print(s)
    


def __starting_point():
    main()
__starting_point()

# list(map(int, input().split()))
n = int(input())
numbers = list(map(int, input().split()))
numbers = sorted(numbers)
ans = 0
for i in range(n // 2):
    ans += (numbers[i] + numbers[n - i - 1]) ** 2
print(ans)

n = int(input())
a = list(map(int,input().split()))
a.sort()
x = a[:len(a)//2]
y = a[len(a)//2:]
sol = 0
for i,j in zip(y, reversed(x)):
    sol += (i+j)*(i+j)
print(sol)

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


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


def li():
    return list(mi())


n = ii()
a = li()
random.shuffle(a)
a = sorted(a)
ans = 0
for i in range(n//2):
    ans += pow(a[i] + a[n-i-1],2)

print(ans)


n = int(input())
l = [*map(int, input().split())]
l.sort()
i, j = 0, n - 1
res = 0
while i <= j:
    res += (l[i] + l[j]) ** 2
    i += 1
    j -= 1
print(res)

n = int(input())
a = [int(j) for j in input().split()]
a.sort()
su = 0
for x in range(int(len(a)/2)):
	# print(a[x], a[n-x-1])
	su += (a[x] + a[n-x-1])**2
print(su)

n = int(input())

cl = list(map(int, input().split()))
cl = sorted(cl)
pos = n//2

res = 0
for i in range(1, n//2+1):
  res+=(cl[n//2-i]+cl[n//2+i-1])**2

print(res)

n = int(input())
M = list(map(int, input().split()))
M.sort()
cnt = 0
for j in range(0, n//2):
    cnt += (M[j] + M[-j - 1])**2
print(cnt)