Щасливі з піцою

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

Черепашки харчуються виключно піцою. Вони вирішили, що день пройшов щасливо, якщо впродовж цього дня не було жодного типу піци, який вони з’їли лише один раз.

Сплінтер приніс \(n\) коробок піци різних типів, утворивши порядок піц в якому їх треба їсти. Відомо, що, з’ївши всі \(n\) піц, черепашки матимуть щасливий день — тобто в усій послідовності немає типу, що зустрічається рівно один раз.

Донателло запропонував розбити початкову послідовність на менші послідовності, причому кожну таку частину вони будуть їсти в окремий день.

Допоможіть черепашкам: порахуйте, на яку максимальну кількість щасливих днів вони можуть розбити своє поїдання піци, розбивши початкову послідовність на неперервні частини так, щоб кожна частина забезпечувала щасливий день.

Вхідні дані

У першому рядку задано одне число \(n\) — кількість піц, що приніс Сплінтер.

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

Вихідні дані

Виведіть одне число — максимальну кількість щасливих днів.

Обмеження

\(2 \le n \le 5 \cdot 10^5\),

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

Приклади