题目描述

HKE 最近热衷于研究序列，有一次他发现了一个有趣的问题：

对于一个序列 $A_1,A_2,\cdots,A_n$，找出两个数 $i,j$（$1\le i<j\le n$），使得 $A_j-A_i$ 最大。

现在给出这个序列，请找出 $A_j-A_i$ 的最大值。

输入格式

第一行为一个正整数 $n$。

接下来 $n$ 行，每行一个整数，第 $(i + 1)$ 行的整数为 $A_i$。

输出格式

一行，为 $A_j-A_i$ 的最大值。

10
1
3
4
6
7
9
10
1
2
9

9

提示

数据规模与约定

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