时空限制

1S/512M

题目描述

Tom 家种了 $n$ 根胡萝卜，每根的大小不同，分别为 $a_1,a_2,\cdots,a_n$，第 $i$ 根胡萝卜的大小为 $a_i$。这天他家里来了 $n$ 个朋友，为了朋友们不认为自己偏心，Tom 希望所有胡萝卜长度相近。

他可以通过一朵神奇的云执行最多一次以下操作：

• 选择一个 $x$ ($1 \le x \le n$)，向前 $x$ 根胡萝卜浇 $x$ 单位的水，这会使前 $x$ 根胡萝卜的大小增大 $x$。

他想使得所有胡萝卜大小的最大值与最小值的差尽量小，请你帮他求出这个值。

输入格式

第一行包含一个整数 $n$ 表示胡萝卜的数量。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 表示胡萝卜的大小。

输出格式

输出一行，包含一个整数表示答案。

样例

样例输入 1

5
3 1 7 4 5

样例输出 1

4

样例输入 2

7
2 6 1 8 4 3 3

样例输出 2

6

数据范围

对于 $100\%$ 的数据，$2 \le n \le 2 \times 10^5$，$1 \le a_i \le 10^9$。