题目描述

小婷和小泽正在参加一次模拟投资活动。小婷记录了连续 $n$ 天的股票价格，小泽负责制定交易方案。

在这 $n$ 天中，他们最多可以买入一股，并在之后的某一天卖出这一股，卖出必须发生在买入之后。

一次交易的收益等于卖出价格减去买入价格。如果无法获得正收益，他们可以不进行交易，此时收益为 $0$。

请帮助小婷和小泽计算能够获得的最大收益。

输入格式

第一行输入一个整数 $n$，表示交易日数量。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，依次表示每天的股票价格。

输出格式

输出一行一个整数，表示最大收益。

样例

4
7 7 1 9

8

考点说明

本题主要考查贪心和前缀最优值。扫描价格时维护此前出现过的最低价格，并用当天价格计算卖出收益，即可在线性时间内得到答案。

输入样例 #2

2
1 2

输出样例 #2

1

输入样例 #3

2
2 1

输出样例 #3

0

数据范围

• 对于 $30\%$ 的数据，$n<1000$；
• 对于 $100\%$ 的数据，$2\le n\le 100000$，$0<a_i\le 10^9$。