Обробка масиву

Обмеження: 2 сек., 512 МіБ

Зеник влаштувався на роботу менеджером із обробки масивів, тож завжди коли в когось виникають труднощі, то Зеник — це єдиний порятунок. Одного дня Шеф доручив Зенику наступне завдання. Задано масив з \(n\) цілих невід’ємних чисел. Назвемо обробкою масиву наступну операцію: від кожного ненульового елементу потрібно відняти найменший ненульовий елемент масиву. Зауважте, що спочатку знаходимо значення найменшого ненульового елементу \(m\) і тоді одночасно від усіх ненульових чисел віднімаємо \(m\). Назвемо масив повністю обробленим, якщо всі його елементи рівні нулю. Завдання Зеника це сказати за яку кількість операцій він зможе повністю обробити масив. Чи зможете допомогти йому із цим?

Вхідні дані

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

Вихідні дані

Виведіть одне число — кількість операцій, необхідну для повної обробки масиву.

Обмеження

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

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

Оцінювання складається з таких блоків:

• по 1 балу за кожен приклад з умови,

• 5 балів: усі \(a_i\) однакові,

• 15 балів: усі \(a_i\) різні,

• 20 балів: \(n \le 300\),

• 31 бал: усі \(a_i\) натуральні,

• 27 балів: без додаткових обмежень.

Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 4 4 4 4	1

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 4 7 4 7 4	2

Примітки

У першому випадку найменшим елементом масиву є 4. Віднявши 4 від кожного елемента ми отримаємо \([0, 0, 0, 0]\). У другому випадку найменшим елементом масиву є 4. Віднявши 4 від кожного елемента ми отримаємо \([0, 3, 0, 3, 0]\). Далі найменшим ненульовим елементом є 3. Віднявши 3 від кожного ненульового елементу, ми отримаємо нульовий масив.

Зауважте, що масив міг бути початково вже обробленим, тобто Зеник за 0 операцій обробить такий масив.