P5146 最大差值

题目描述

HKE 最近迷上了研究序列。他提出了这样一个问题： 给定一个序列 \(A_1, A_2, \ldots, A_n\)，选择一对下标 \(i, j\)（满足 \(1 \le i < j \le n\)），使得差值 \(A_j - A_i\) 尽可能大。 请输出这个最大差值。

输入格式

• 第一行：一个正整数 \(n\)。
• 接下来 \(n\) 行：第 \((i+1)\) 行给出一个整数，表示 \(A_i\)。

输出格式

• 一行输出 \(\max(A_j - A_i) {1 \le i < j \le n}\) 的值。

样例

输入

10
1
3
4
6
7
9
10
1
2
9

输出

9

说明/提示

• 对于 \(30%\) 的数据，\(n \le 1000\)；
• 对于 \(70%\) 的数据，\(n \le 10^5\)；
• 对于 \(100%\) 的数据：\(2 \le n \le 10^6\)，且 \(A_i\) 在 int 范围内。