10.1 : 正三角形

10.1

P6 : 正三角形

描述

有 $n$ 根棍子，长度依次为 $a_1,a_2...a_n$ 。可以执行以下操作任意次（可能为0）：

1、选择一根木棍，然后将其长度增加1.

2、选择一根木棍，然后将其长度减少1.

注意：变化过程中必须保证木棍长度为正整数。

至少执行多少次操作能在这些木棍中找到3根组成一个正三角形（等边三角形）？

输入

第一行一个整数 $n$ 表示木棍数量。

第二行 $n$ 个整数 $a_1,a_2...a_n$ ，依次表示每根木棍长度。

对于100%的数据：

$3\le n \le 300$

$1\le a_i \le 10^9$

输出

一行，一个表示最少操作次数的整数。

样例

输入

3
1 2 3

输出

输入

4
7 3 7 3

输出

输入

5
3 4 2 1 1

输出