Array Processing

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Zenyk got a job as an array processing manager, so whenever anyone has difficulties, Zenyk is the only salvation. One day, the Boss assigned Zenyk the following task. You are given an array of \(n\) non-negative integers. Let’s call the array processing operation the following: we need to subtract the smallest non-zero element of the array from each non-zero element. Note that we first find the value of the smallest non-zero element \(m\) and then simultaneously subtract \(m\) from all non-zero numbers. Let’s call an array fully processed if all its elements are equal to zero. Zenyk’s task is to state how many operations it will take him to fully process the array. Can you help him with this?

Input

The first line contains an integer \(n\) — the size of the array. The next line contains \(n\) integers — the array \(a_i\).

Output

Print a single number — the number of operations required to fully process the array.

Constraints

\(1 \leq n \leq 2 \cdot 10^5\),

\(0 \leq a_i \leq 10^6\).

Evaluation consists of the following subtasks:

• 1 point for each example from the statement,

• 5 points: all \(a_i\) are equal,

• 15 points: all \(a_i\) are distinct,

• 20 points: \(n \le 300\),

• 31 points: all \(a_i\) are positive integers,

• 27 points: no additional constraints.

You will get the points for a subtask only if your solution passes all tests in that subtask.

Samples

Input (stdin) сopy	Output (stdout) сopy
4 4 4 4 4	1

Input (stdin) сopy	Output (stdout) сopy
5 4 7 4 7 4	2

Notes

In the first case, the smallest element of the array is 4. Subtracting 4 from each element we get \([0, 0, 0, 0]\). In the second case, the smallest element of the array is 4. Subtracting 4 from each element we get \([0, 3, 0, 3, 0]\). Next, the smallest non-zero element is 3. Subtracting 3 from each non-zero element, we get a zero array.

Note that the array could initially already be processed, meaning Zenyk will process such an array in 0 operations.