题目描述

你现在要来炒股了，假设你一开始有无限多的钱，而且你能够成功的预测接下来N天每天股票的价格。

每天，你必须要做以下2件事的其中一件：

你可以买入当天的股票一股，价格是Pi。

你可以卖出当天的股票一股，价格也是Pi。

现在的问题是N天以后，你最多可以赚到多少钱。

注意，如果你到最后还有没有卖出的股票，那么这些股票是不能算到你的收益里面的。

显然，你开始的时候，什么股票的都没有，只有钱。

输入

输入的第一行是一个正整数，表示天数。
接下来有个正整数，表示第天股票的价格。

输出

输出最多可以赚的钱。

样例输入

样例输入1:

8

2 5 4 3 7 1 8 6

样例输入2:

5

10000 1000 100 10 1

样例输入3:

15

300 1 4000 1 50000 900000000 20 600000 50000 300 50000 80000000 900000000 7000000 900000000

样例输出

样例输出1:

16

样例输出2:

0

样例输出3:
2787595378

提示

1≤n≤2*10^5

1≤Pi≤10^9