Problem Background

Grateful thanks to the whk genius Fan Ju/bx

Despite Fan Ju's strong academic performance, he doesn't want to put too much pressure on his peers during the New Year. Therefore, he plans to manipulate his annual exam results...

Problem Description

Looking at his soaring grades like a dragon, Fan Ju couldn't help but sing "Love You" as the New Year approached.

He had a total of $n$ exams this year, with the rank in the $i$-th exam being $a_i$.

This无形中给其他同学造成了压力，于是他希望重新排列自己的 $n$ 次排名，使得进步最大的一次考试进步的名次最少，这样他就可以隐藏自己的实力。

对于第 $i$ 次和第 $i+1$ 次考试（$1\le i < n$），他的进步名次即为 $a_i-a_{i+1}$，如果该值为负则代表他退步了。

Please help him.

Input Format

Input consists of two lines.

The first line contains an integer $n$.

The second line contains $n$ integers separated by spaces, where the $i$-th integer represents $a_i$.

Output Format

Output a single integer, which is the answer.

Sample Input and Output

Sample Input #1

2
1 1

Sample Output #1

0

Sample Input #2

4
2 4 1 3

Sample Output #2

-1

Notes

Sample 1 Explanation

Fan Ju does not change the original sequence of exams, so he progresses by $0$ ranks from the first to the second exam (the rank remains unchanged).

Sample 2 Explanation

Fan Ju can rearrange his exam ranks to $1, 2, 3, 4$, so he progresses by $-1$ each time, hence the answer is $-1$.

This problem uses bundled testing.

Data Range

• For $30\%$ of the data, $n \le 10$.
• For $50\%$ of the data, $n \le 5000$.
• For an additional $20\%$ of the data, $a_i \le 2$.
• For $100\%$ of the data, $2 \le n \le 10^6$, $1 \le a_i \le 10^9$.

见题面 Input 部分

见题面 Output 部分