背景

Python 用户建议使用 PyPy3 提交本题。

题目描述

给定一个包含 $n$ 个数的序列 $A_i$，每次操作可以选择其中任意一个数将其 $+1$ 或 $−1$。

我们要让这个序列满足能够从中任选三个数，这三个数对应长度的三条边总能组成一个等腰三角形。问最少需要多少次操作才能让序列满足条件。

输入格式

输入的第一行包含一个整数 $n$。

第二行包含 $n$ 个整数，分别表示 $A_1, A_2, \cdots, A_n$，相邻两个整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数，表示最少的操作次数。

5
3 3 5 7 7

3

提示

对于 $40\%$ 的评测用例，$n \le 5000,A_i \le5000$；

对于 $70\%$ 的评测用例，$n \le 2 \times 10^5,A_i \le 10^6$；

对于所有评测用例，$1 \le n \le 2 \times 10^5,1 \le A_i \le 10^9$。

样例解释

将原序列修改为 $4, 4, 4, 7, 7$ 即可。