Nông dân John đang thử nghiệm một cách mới để tăng năng suất trồng cỏ của mình, đó là tận dụng vi khuẩn có lợi. Tuy nhiên cái gì quá nhiều hay quá ít thì cũng không tốt nên anh đã đặt ra "mức vi khuẩn" để dễ dàng kiểm soát sự tăng trưởng của hàng cỏ của mình.

Anh John trồng hàng cỏ gồm \(N\) (\(1 \leq N \leq 2 \times 10^5\)) cụm cỏ dọc theo trục số, trong đó cụm cỏ thứ \(i\) có mức vi khuẩn chênh lệch với mức tiêu chuẩn \(a_i\). Ví dụ nếu \(a_i = -1\) thì cụm cỏ \(i\) có ít hơn mức tiêu chuẩn 1 đơn vị.

Nhiệm vụ của bạn là giúp anh John phun thuốc lên hàng cỏ, sao cho mọi cụm cỏ đều có mức vi khuẩn tiêu chuẩn bằng loại máy phun đặc biệt có thể đổi giữa tăng giảm mức vi khuẩn và mức năng lượng. Mỗi lần phun, bạn sẽ phun từ đầu bên phải của hàng cỏ đến hàng cỏ cách đó \(L\) đơn vị, thêm vào đó, cứ cụm cỏ cách bạn \(i\) thì sẽ nhận ít hơn \(N-i\) hiệu ứng tăng giảm, nghĩa là cụm cỏ ở vị trí \(N-1\) sẽ tăng 2 mức vi khuẩn nếu máy phun đang ở mức năng lượng 3.

Hãy hoàn thành công việc anh John giao cho bạn với số lần phun ít nhất có thể.

Input

• Dòng đầu tiên chứa \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(a_{1}...a{n}\) là mức vi khuẩn ban đầu của hàng cỏ

Output

• Gồm một số nguyên duy nhất là số lần phun ít nhất có thể để hoàn thành công việc.

Scoring

• Subtask \(1\): \(N \leq 10^{3}\), kết quả lớn nhất không quá 10^{3}.
• Subtask \(2\): \(N \leq 10^{3}\)
• Subtask \(3\): Không có ràng buộc gì thêm.

2
-1 3

6

5
1 3 -2 -7 5

26