← 返回题目列表

Codeforces · 394/D

D. 体育和包子

中文机器翻译题面 查看原题

SESC的体育老师也是一位数学家。他最喜欢的数学主题是级数。这就是为什么老师希望学生以不递减的高度排列成等差数列。

为了达到目的,体育老师从餐厅订了很多神奇的包子。魔法包子有两种:学生吃第一种魔法包子时,身高会增加一岁;吃第二类魔法包子时,身高会减少一岁。体育老师果然是关心学生的健康,所以不希望他们吃很多包子。更准确地说,他希望某个学生吃的包子的最大数量最少。

帮助老师,获得一些学生必须吃的最大数量的包子才能实现老师的目标。另外,获取实现目标的可能方法之一,即最终最低学生的身高以及最终进展的步数。

输入

单行包含整数 n (2 ≤ n ≤ 103) — 学生人数。第二行包含 n 个空格分隔的整数——所有学生的身高。一名学生的身高是一个绝对值不超过104的整数。

输出

在第一行打印出某个学生为达到老师的目的而吃掉的最大包子数量。在第二行中,打印两个以空格分隔的整数 - 最后最低学生的身高和级数的步数。请注意,步长必须为非负数。

如果有多个可能的答案,您可以打印其中任何一个。

示例

输入 #1

5
-3 -4 -2 -3 3

输出 #1

2
-3 1

输入 #2

5
2 -3 -1 -4 3

输出 #2

1
-4 2

注意

让我们看一下第一个示例。我们可以按照以下方式进行:

- 不要喂第一个学生,他的身高将保持等于-3;
- 给第二个学生两个第一种类型的发髻,他的高度变成等于-2;
- 给第3个学生两个第一种类型的发髻,他的高度变为0;
- 给第4个学生两个第一种类型的发髻,他的高度变成等于-1;
- 给第5个学生两个第二种类型的发髻,他的高度变成等于1。

综上所述,当学生按非递减身高排队时,将是一个等差数列:-3,-2,-1,0,1。最低学生的身高等于-3,级数的步长等于1。一个学生最多吃的包子数量等于2。