Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P183PROC - ROUND 3C - Đôi bạn thân

Dark Magican và QQMM là đôi bạn thân, cả hai đều rất thích tựa game Liên Quân Mobile và thường xuyên leo rank cùng nhau. Trong trận đấu quyết định để lên cao thủ của Dark Magician, vì tính hay troll bạn bè, QQMM đã phá game khiến Dark Magician không lên được cao thủ. Dark Magician rất tức giận nên đã block QQMM. QQMM cảm thấy hối hận nên đã đến xin Dark Magician tha lỗi. Dark Magician tính thù dai nên yêu cầu QQMM phải giải được bài toán anh đưa ra thì mới tha lỗi. Vốn thông minh từ nhỏ nên QQMM đã nhận lời ngay. Tuy nhiên, bài toán Dark Magician đưa ra không hề dễ dàng, một mình QQMM không thể nghĩ ra được nên đành cầu cứu các bạn PTIT. Các bạn hãy giúp QQMM lấy lại tình bạn nhé! Bài toán như sau :

Một dãy số được gọi là đẹp nếu nó là dãy số tăng dần (tức là với mọi i, j i < j thì a< aj). Cho một dãy số an phần tử. Trong mỗi lượt bạn có thể chọn bất kì phần tử nào trong dãy và tăng hoặc giảm nó đi 1 đơn vị. Mục đích là làm cho dãy số trở nên đẹp. Bạn được phép thay đổi các phần tử thành bất kì giá trị nào, kể cả thành âm hoặc bằng 0. Nhiệm vụ của bạn là tìm ra số lượt tối thiểu để biến đổi dãy số đã cho thành dãy đẹp.

Input

Dòng đầu tiên chứa số nguyên n – độ dài của dãy số (1 ≤ n ≤ 3000).

Dòng tiếp theo chứa n số nguyên ai (1 ≤ ai ≤ 109).

Output

Số nguyên duy nhất – đáp án bài toán của Dark Magician.

Example

Test 1:
Input:
2
1 10000 Output: 0
Test 2:
Input:
5
1 1 1 2 3
Output:
3

Được gửi lên bởi:adm
Ngày:2018-03-16
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.