题目背景

BAPC 包裹中心的仓库刚刚收到了安全检查警告。过去，多个箱子可以堆放在同一个货位；但按照最新规定，每个货位最多只能放置一个箱子。工作人员必须尽快重新安排所有箱子的位置。

箱子移动后，自动取件机器人也要重新记录它们的新位置。一个箱子若移动了 $d$ 个位置，重新编程所需的时间为 $d^2$。

题目描述

一条无限长的整数数轴上放置着 $n$ 个箱子，第 $i$ 个箱子的初始位置为 $x_i$。多个箱子可能位于同一个位置。

你可以把每个箱子移动到任意整数位置。移动结束后，所有箱子所在的位置必须两两不同。

若一个箱子从位置 $x$ 移动到位置 $y$，产生的代价为

求使所有箱子位置互不相同所需的最小总代价。

仓库在数轴的左右两个方向上均没有边界。

例如，在样例 $1$ 中，可以按照下图移动箱子，总代价为

样例 1 的一种最优移动方案

输入格式

第一行包含一个整数 $n$（$1\le n\le 10^6$），表示箱子数量。

第二行包含 $n$ 个整数 $x_1,x_2,\ldots,x_n$（$|x_i|\le 10^9$），表示各箱子的初始位置。

保证输入的位置按非递减顺序给出，即

输出格式

输出一个整数，表示使所有箱子最终位置两两不同的最小总代价。

样例 1

输入

7
-1 -1 3 3 3 3 4

输出

8

样例 2

输入

8
2 2 2 2 2 2 4 4

输出

24