该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

在遥远的未来，年轻的工程师Orange接到了一项至关重要的任务：为即将启航的“探索号”星际飞船充能。

飞船的能量核心由 $n$ 个串联的能量槽构成，编号从 $1$ 到 $n$。为了维持核心的稳定，奇数编号的能量槽（$1, 3, 5, ...$）被设计为“增幅器”，会放大输入的能量；而偶数编号的能量槽（$2, 4, 6, ...$）则是“稳定器”，会抵消一部分能量。

Orange手上有 $n$ 个能量各不相同的能量晶体，第 $i$ 个晶体的基础能量值为 $a_i$。当一个基础能量为 $a_i$ 的晶体被放入第 $j$ 个能量槽时，它对核心总能量贡献为 $a_i^2$。如果 $j$ 是奇数，贡献为 $+a_i^2$；如果 $j$ 是偶数，贡献为 $-a_i^2$。

Orange可以自由决定将这些晶体放入哪个能量槽（即可以任意重排序列 $a$）。他的目标是最大化能量核心的总输出能量。

请你帮助Orange计算出，在最优的摆放方案下，能量核心能达到的最大总能量是多少。

Format

Input

第一行输入一个整数 $n (1 ≤ n ≤ 10^5)$，表示能量槽和晶体的数量。 第二行输入 $n$ 个整数 $a_1, a_2, ..., a_n (0 < a_i < 10^5)$，表示每个晶体的基础能量值。

Output

输出一行一个整数，表示能量核心能达到的最大总能量。

Samples

5
1 2 3 4 5

45