Dim4ou is a famous BG rapper who was one day accidentally hit by a thunderbolt. From that day on Dim4ou started seeing everything in numbers, but not in black and green as Neo from the Matrix and instead in black and yellow (as Wiz Khalifa). What Dim4ou encountered is that these numbers are actually the price of gold ($$$).
As he knows the price of gold ounce for the next N days you need to help him maximize the potential profit. What you can do on each day is to either buy one ounce, sell any number of ounces that you already own, or not make any transaction at all. Your end goal is to calculate the maximum profit you and Dim4ou can obtain with an optimal trading strategy.
- Input is read from the console
- On the first line in the console is a number N denoting the N days for which you will know the price per ounce.
- The second line contains N integers separated by white space, denoting the predicted price per gold ounce for the next N days.
- Output should be printed on the console
- A single line denoting the maximum profit which can be obtained.
- 1 <= N <= 50000
- 1 <= price per ounce <= 100000
- Time limit: 0.1s
- Memory limit: 16 MB
Sample test 1
4 1 2 1 2
Sample test 2
3 10 7 5
Sample test 3
3 1 3 200