ZOJ Problem Set - 3512
Bernard Madoff is an American former stock broker, investment adviser, non-executive chairman of the NASDAQ stock market, and the admitted operator of what has been described as the largest Ponzi scheme in history.
Two programmers, Jerome O'Hara and George Perez, who helped Bernard Madoff program to produce false records have been indicted. They were accused of conspiracy, falsifying records of a broker dealer and falsifying records of an investment adviser.
In every quarter of these years, the two programmers would receive a data sheet, which provided a series of profit records a1 a2 ... aN in that period. Due to the economic crisis, the awful records might scare investors away. Therefore, the programmers were asked to falsifying these records into b1 b2 ... bN. In order to deceive investors, any record must be no less than all the records before it (it means for any 1 ≤ i < j ≤ N, bi ≤ bj).
On the other hand, they defined a risk value for their illegal work: risk value = | a1 - b1 | + | a2 - b2 | + ... + | aN - bN | . For example, the original profit records are 300 400 200 100. If they choose 300 400 400 400 as the fake records, the risk value is 0 + 0 + 200 + 300 = 500. But if they choose 250 250 250 250 as the fake records, the risk value is 50 + 150 + 50 + 150 = 400. To avoid raising suspicion, they need to minimize the risk value.
Now we will give you some copies of the original profit records, you need to find out the minimal possible risk value.
There are multiple test cases (no more than 20).
For each test case, the first line contains one integer N (1 ≤ N ≤ 50000), the next line contains N integers a1 a2 ... aN (-109 ≤ ai ≤ 109). The input will end with N = 0.
For each test case, print a single line that contains minimal possible risk value.
4 300 400 200 100 0
Author: JIANG, Kai
Contest: ZOJ Monthly, July 2011