Bậc Thang Nguyên

Cho dãy số nguyên $A$. Hãy chọn dãy số nguyên $B$ tăng nghiêm ngặt để tổng $|A_i-B_i|$ nhỏ nhất và in chi phí nhỏ nhất.

Input

• Dòng đầu chứa $N$.
• Dòng tiếp theo chứa $A_1,\dots ,A_N$.

Output

• In một số nguyên là chi phí nhỏ nhất.

Constraints

• $1\le N\le 10^6$.
• $0\le A_i\le 2\cdot 10^9$.
• Các trường hợp ngữ nghĩa quan trọng:
  • $C_{01}$: $N=1$. Không cần thay đổi phần tử nên chi phí bằng $0$.
  • $C_{02}$: $A$ đã tăng nghiêm ngặt. Có thể chọn $B=A$ và chi phí bằng $0$.
  • $C_{03}$: $A$ giảm mạnh. Nhiều phần tử phải được gom về các mức biến đổi.
  • $C_{04}$: Giá trị gần $2\cdot 10^9$. Phép tính tổng phải dùng số nguyên $64$ bit.

Scoring

• Subtask $1$ ($50$ điểm): $10$ test đầu có kích thước nhỏ, phù hợp với lời giải vét cạn mô tả trong tài liệu.
• Subtask $2$ ($50$ điểm): Không có giới hạn bổ sung.

Example

5
5 4 3 8 8

5