Hùng đang được giao nhiệm vụ sắp đặt hàng hoá trong nhà kho. Hàng hoá đã được đóng thành pallet, là các khối vuông kích thước 1 đơn vị. Hiện tại, các pallet được sắp xếp thành các hàng, Hùng sẽ xử lý riêng từng hàng. Mỗi hàng có thể được mô tả bởi một dãy số nguyên không âm ~a=a_1, a_2, \ldots, a_n~, cho biết vị trí thứ ~i~ ở trong hàng này được xếp ~a_i~ pallet chồng lên nhau. Để dễ quan sát và dỡ hàng, Hùng muốn cách sắp đặt thoả mãn tính chất: Các pallet phải được xếp thành các chồng, chồng sau không thấp hơn chồng trước. Cậu có thể thực hiện nhiều thao tác sắp đặt, mỗi thao tác là xếp thêm một pallet vào một chồng nào đó, hoặc dỡ bớt một pallet ở một chồng nào đó. Hùng muốn thực hiện ít nhất các thao tác để đạt được tính chất mong muốn. Cụ thể hơn, bạn được cho một dãy số nguyên không âm ~a=a_1, a_2, \ldots, a_n~. Bạn có thể biến đổi dãy số này, mỗi bước chọn một số trong dãy và tăng số đó lên 1 đơn vị hoặc giảm số đó đi 1 đơn vị, sao cho trong quá trình biến đổi dãy luôn không âm và cuối cùng thu được một dãy không giảm. Hãy tìm số phép biến đổi ít nhất có thể.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \leq n \leq 5000~);

• Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1, a_2, \ldots, a_n~ (~a_i \leq 10^9\ \forall i=1, 2, \ldots, n~).

Output

Ghi một số tự nhiên là số bước biến đổi ít nhất.

Sample Input 1

5
1 4 2 5 2

Sample Output 1

5

Sample Input 2

9
1 3 5 3 6 3 4 3 7

Sample Output 2

6

Sample Input 3

6
6 5 4 3 2 1

Sample Output 3

9

Sample Input 4

10
1 2 3 4 6 6 8 8 9 10

Sample Output 4

0

Sample Input 5

4
2326153 2340498 6409535 5774211

Sample Output 5

635324