HZNUOJ

KK买股票

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:870     AC:191     Score:92.21

Description

KK在股票模拟软件里看到了一只名为“蛇蛇股份”的股票,他觉得这只股票很有潜力。

KK有一个能力,他可以看到接下来$N$天里“蛇蛇股份”的价格,因此他也受到了限制,在这N天他最多只能买入和卖出一次股票(显然,他卖股票的前提条件是持有股票),请聪明的你帮KK计算一下他在这N天最多可赚多少钱(KK初始拥有无限多的钱)。

Input

第一行是一个整数$N(2 \leq N \leq 10^5)$。
第二行有$N$个整数,第$i$个整数表示第$i$天一手蛇蛇股份的价格$p_i(1 \leq p_i \leq 10^3)$。

Output

输出KK最多可以赚的钱(如果没有赚到钱的方案,即不管怎么样都会亏钱,就输出$0$)。

Samples

input
6 10 1 7 3 8 6
output
7
input
3 8 3 2
output
0

Hint

样例1中,在第二天买入一手,第五天卖出一手,赚得8-1=7元

样例2中,KK不管在哪天买入,再卖都赚不到钱,输出0

Author

GAO, Xiaoyun