#1078. 最大差值

最大差值

最大差值

题目描述

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

对于一个序列 A1,A2,,AnA_1,A_2,\cdots,A_n,找出两个数 i,ji,j1i<jn1\le i<j\le n),使得 AjAiA_j-A_i 最大。

现在给出这个序列,请找出 AjAiA_j-A_i 的最大值。

输入格式

第一行为一个正整数 nn

接下来 nn 行,每行一个整数,第 (i+1)(i + 1) 行的整数为 AiA_i

输出格式

一行,为 AjAiA_j-A_i 的最大值。

样例 #1

样例输入 #1

10
1
3
4
6
7
9
10
1
2
9

样例输出 #1

9

提示

数据规模与约定

  • 对于 30%30\% 的数据,n1000n\le1000
  • 对于 70%70\% 的数据,n105n\le10^5
  • 对于 100%100\% 的数据:2n1062\le n\le 10^6AiA_i 在 int 范围内。