#2550. 路面修整

路面修整

Description

一条笔直的道路连接着约翰农场的两块田地,但它变化的海拔高度超出了约翰的想象。约翰希望添加或清除道路上的泥土,使其成为一个单调的斜坡(向上或向下倾斜)。给定NN个整数A1,,AN0Ai1081N2000A_1,…,A_N(0≤A i≤10^8,1≤N≤2000),用于描述道路上NN个等距位置的海拔高度。将这些海拔高度调整为新的非递增或非递减序列B1,,BNB_1,…,B_ N。由于在道路沿线的任何位置添加或清除泥土的费用都相同,因此修改道路的总费用为A1B1+A2B2++ANBN|A_1-B_1|+|A_2-B_2|+…+|A_N-B_N|,请计算道路修整的最小成本,答案为不大于3232位的整数。

Format

Input

11行输入单个整数NN;接下来的NN行,每行都包含一个整数AiA_i,表示海拔高度。

Output

输出对道路进行坡度调整的最小成本,使其在海拔高度上非递增或非递减。

Samples

7
1
3
2
4
5
3
9
3

来源

POJ3666