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

Limits: 3 sec., 512 MiB

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

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

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

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

Input

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

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

Output

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

Constraints

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

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

Samples