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

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

3 секунди
512 мегабайтів
Дуже складна

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

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

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

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

Вхідні дані

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

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

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

1 \le a_i \le 10^9.

Вихідні дані

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

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading