Нульовий масив

Limits: 2 sec., 256 MiB

У Зеника є масив \(a\) з \(n\) цілих чисел.

За одну операцію Зеник може вибрати будь-який відрізок масиву завдовжки більше за 1. Позначимо \(\lceil x \rceil\) середнє арифметичне на цьому відрізку, заокруглене вверх. Для кожного елемента масиву Зеник зробить \(a_i := \max (0, a_i - \lceil x \rceil)\).

Допоможіть Зенику — скажіть, за яку мінімальну кількість операцій усі елементи масиву стануть рівними нулю.

Input

У першому рядку задано ціле число \(n\) — довжину масиву.

У другому рядку задано \(n\) цілих чисел \(a_i\) — елементи масиву.

Output

У єдиному рядку виведіть ціле число — відповідь на задачу.

Constraints

\(1 \le n \le 10^5\),

\(0 \le a_i \le 10^9\).

Samples