T429110 「YAC Round 6」琪露诺的实力隐藏法


琪露诺这学期在稗田寺子屋一共有 $n$ 次考试，她第 $i$ 次考试的排名为 $a_i$。 琪露诺决定隐藏实力，于是她打算把自己 $n$ 次考试排名进行重排，**使得进步最大的一次进步的名次最少。** 第 $i$ 次考试到第 $i + 1$ 次考试的进步名次为 $a_i - a_{i+1}$，如果 $a_i - a_{i+1} > 0$，进步的名次为正数，表示排名上升；如果 $a_i - a_{i+1} < 0$，进步的名次为负数，表示排名下降。 请你帮琪露诺找到一个隐藏实力的重排方法，使得 **进步最大的一次进步的名次最少**。输出重排后 **最大的进步名次**。

第一行，输入一个整数 $n$。 第二行，输入 $n$ 个整数， $a_1, a_2, \ldots , a_n$ 。 $a_i$ 表示第 $i$ 次考试的名次。

输出一行一个整数，表示重排后 **最大的进步名次**。

#### 样例 1 解释 琪露诺不改变原本的考试序列，最少的进步名次为 $0$。 #### 样例 2 解释 重排前最大的进步名次为 $5$。琪露诺可以把自己的考试排名重排为 $4$ $8$ $9$，最大的进步名次为 $-1$。 #### 数据范围 $2\le n\le 10^6$，$1\le a_i\le 10^9$。