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

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

3 seconds
512 megabytes
Very hard

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

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

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

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

Input

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

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

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

1 \le a_i \le 10^9.

Output

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

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Example 2

Loading
Loading