ami có \(n\) đống sỏi, được đánh số từ \(1\) đến \(n\). Ở một thao tác, ami có thể thêm vào đống sỏi \(i\) 1 viên sỏi, hoặc vứt \(1\) viên sỏi ra khỏi đống sỏi \(i\). ami cần tìm số thao tác ít nhất để đám sỏi được sắp xếp tăng dần theo số sỏi (\(a_i < a_{i+1}\) với mọi \(1 \leq i < n\)).

Lưu ý rằng, đây là đống sỏi ma thuật, vì vậy số sỏi trong 1 đống có thể âm hoặc bằng 0.

Input

• Dòng đầu tiên chứa 1 số nguyên dương \(n\) là số đống sỏi.
• Dòng tiếp theo chứa \(n\) số nguyên dương \(a_i\) là số sỏi trong đống \(i\).

Output

• Một số nguyên là số thao tác ít nhất.

Example

3
3 3 3

2

2
1 99

0

Giới hạn

• \(33\%\) test có \(1 \leq n \leq 3000\), \(a_i \leq 5000\).
• \(67\%\) test có \(1 \leq n \leq 3000\), \(a_i \leq 10^9\).