
ZOJ Problem Set  3512
Bernard Madoff is an American former stock broker, investment adviser, nonexecutive 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 a_{1} a_{2} ... a_{N} 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 b_{1} b_{2} ... b_{N}. 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, b_{i} ≤ b_{j}). On the other hand, they defined a risk value for their illegal work: risk value =  a_{1}  b_{1}  +  a_{2}  b_{2}  + ... +  a_{N}  b_{N}  . 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. InputThere 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 a_{1} a_{2} ... a_{N} (10^{9} ≤ a_{i} ≤ 10^{9}). The input will end with N = 0. OutputFor each test case, print a single line that contains minimal possible risk value. Sample Input4 300 400 200 100 0 Sample Output400 Author: JIANG, Kai Contest: ZOJ Monthly, July 2011 