Zero Array

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenik has an array \(a\) of \(n\) integers.

In one operation, Zenik can choose any subarray of length greater than 1. Let \(\lceil x \rceil\) denote the arithmetic mean on this subarray, rounded up. For each element of the array, Zenik will do \(a_i := \max (0, a_i - \lceil x \rceil)\).

Help Zenik — tell him the minimum number of operations required to make all elements of the array equal to zero.

Input

The first line contains an integer \(n\) — the length of the array.

The second line contains \(n\) integers \(a_i\) — the elements of the array.

Output

In a single line, output an integer — the answer to the problem.

Constraints

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

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

Samples