Minimize Maximum Exam Improvement

Faced with his soaring exam rankings, Fan Fan wants to hide his true abilities by minimizing the most impressive improvement between consecutive exams. He had a total of (n) exams with rankings (a_1, a_2, \ldots, a_n). For every two consecutive exams ((i) and (i+1)), the improvement is defined as (a_i - a_{i+1}). Note that if (a_i - a_{i+1}) is negative, it indicates a drop in performance rather than an improvement. To conceal his actual prowess, Fan Fan wishes to reorder his exam rankings so that the maximum improvement is as low as possible. In particular, if no improvement occurs, the maximum improvement is considered to be 0. Your task is to compute this minimized maximum improvement. (\newline)(\textbf{Observation:}) Since a reordering into non-decreasing order is always possible, all differences (a_i - a_{i+1}) will be non-positive. In that case, if the improvement is defined as (\max(0, a_i - a_{i+1})), the maximum improvement will always be 0.

inputFormat

The first line contains an integer (n) ((1 \le n \le 10^5)), representing the number of exams.\nThe second line contains (n) space-separated integers (a_1, a_2, \ldots, a_n) indicating the ranking in each exam.

outputFormat

Output a single integer: the minimized maximum improvement after optimally reordering the exam rankings.

sample

3
3 1 2

0