Bạn phụ trách phát triển các khu đất mới ở ngoại ô Toruń. Bạn đã quyết định xây dựng một con đường chính với \(n\) khu đất dọc theo đường, được đánh số từ \(1\) đến \(n\). Địa hình nơi đây hơi đồi núi, và độ cao của khu đất thứ \(i\) là \(a_i\) xentimét.

Hóa ra không ai muốn mua một khu đất nằm trên đoạn dốc. Cụ thể, với dãy độ cao \(a_1,a_2,\ldots,a_n\), một đoạn dốc là một dãy con liên tiếp \(a_{i-1},a_i,\ldots,a_j,a_{j+1}\) với \(2\le i\le j\le n-1\), thỏa mãn một trong hai điều kiện:

hoặc

Nói cách khác, đây là một đoạn gồm các khu đất ở vị trí \(i-1,i,\ldots,j,j+1\), trong đó mọi khu đất từ vị trí \(i\) đến vị trí \(j\) đều có cùng độ cao \(h\), và \(h\) lớn hơn độ cao ở một đầu, đồng thời nhỏ hơn độ cao ở đầu còn lại.

Bạn có thể tăng hoặc giảm độ cao của mỗi khu đất một lượng nguyên tùy ý, nhưng muốn tổng lượng thay đổi là nhỏ nhất. Hãy xác định tổng lượng thay đổi độ cao nhỏ nhất để không còn đoạn dốc nào. Tức là, cần tìm một dãy độ cao \(b_1,b_2,\ldots,b_n\) không có đoạn dốc sao cho giá trị sau nhỏ nhất:

Các độ cao \(b_i\) phải là số nguyên, không nhất thiết phải dương, và không chịu bất kỳ ràng buộc nào khác.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(n\), là số khu đất dọc theo con đường.

Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\), trong đó \(a_i\) là độ cao ban đầu của khu đất thứ \(i\).

Dữ liệu ra

In ra tổng lượng thay đổi độ cao nhỏ nhất để không còn đoạn dốc nào.

Ràng buộc

• \(1\le n\le 2\cdot 10^5\).
• \(0\le a_i\le 10^9\) với mọi \(1\le i\le n\).

Phân nhóm

1. \(4\) điểm: \(n\le 5\) và \(a_i\le 10\) với mọi \(1\le i\le n\).
2. \(13\) điểm: \(n\le 2000\).
3. \(8\) điểm: \(a_i\le 10\) với mọi \(1\le i\le n\).
4. \(19\) điểm: \(a_i<a_{i+1}\) với mọi \(1\le i<n\).
5. \(29\) điểm: \(n\le 2\cdot 10^4\).
6. \(27\) điểm: không có ràng buộc bổ sung.

Ví dụ

11
7 2 1 2 5 7 8 8 10 8 8

5