Description

20有一个长度为n，由正整数构成的a数组，和一个长度为n，每个元素都为0的b数组。（对于 0 ≤ i ≤ n 都有b[i] = 0）
在一次操作中，你可以选择一个i（0 ≤ i ≤ n），并从b[i]中添加一个a[i]或者减去一个a[i]
众所周知，20患有严重的递增玉玉症 ，他希望b数组能够符合递增规律（即，每个元素都严格大于它之前的每一个元素），否则他就会昼夜难眠。
现在，希望你帮帮20，找到让b数组递增的最小操作数，让他能够睡香香。

Format

Input

第一行输入一个整数n（2 ≤ n ≤ 5000）。
第二行输入n个整数：a1 , a2, ..., an (1 ≤ ai ≤ 1e9)

Output

打印使b数组递增的最小操作数并换行

Sample 1

Input

5
1 2 3 4 5

Output

4

Note

对于案例1，你可以从b1中减去a1，并分别添加a3,a4,a5到b3,b4,b5中。
四次移动之后，最终的b数组为[-1,0,3,4,5]

Sample 2

Input

7
1 2 1 2 1 2 1

Output

10

Limitation

1s, 1024KiB for each test case.

Source

每日一题