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

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