Description

一个长度为N的数列A1，A2，…,AN,现在让你把它调整成另外一个单调数列B1，B2，…,BN.单调的意思是要么不增要么不减. 调整的方式是把Ai增大或者缩小变成Bi.

调整的费用M为:

M=|A1 - B1| + |A2 - B2| + ... + |AN - BN |

你的任务是计算最小的M

Input

输入包含多组数据,每组数据第一行是一个整数N(N<=20000),接下来是N个整数.

Output

输出调整的最小花费.

Sample

Input

4
0
3
1
2

4
3
2
0
1

Output

2
1

Source: zjut_DD