该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

n天
每天股票有一个不同的价格。
你每天可以买入或者卖出一股股票。（只能进行at most一种操作）
一开始你除了很多很多钱之外，一无所有。
你需要知道n天之后你最多能够通过买入、卖出股票赚到多少钱（所有都卖出去）。

Input

第一行一个正整数n为天数（n<=300000）
第二行n个正整数pi（p<=1000000）

Output

一个正整数，你能赚到的钱的最大值

Sample 1

Input

8
6125 14994 20374 26342 30291 32416 24039 17338 

Output

47556

Limitation

1s, 128Mb for each test case.

Hint

Source

lyhlyhlyh