开始 2022-10-03 09:00:00

10.1

结束 2022-10-04 17:25:00
比赛已经结束
当前 2024-11-20 00:45:16

F. 正三角形

描述

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

输出

2

输入

4
7 3 7 3

输出

4

输入

5
3 4 2 1 1

输出

1

提交

登录

注册
时间限制 1000 毫秒
内存限制 128 MB
提交