Selon le dictionnaire PWN, un « leader » est, entre autres, « le chef d'un parti politique, d'un syndicat ou d'autres organisations sociales ». En algorithmique, cependant, on appelle leader d'une séquence d'éléments un élément dont le nombre d'occurrences est strictement supérieur à la moitié de la longueur de la séquence. Par exemple, le leader de la séquence $[7, 2, 5, 7, 7]$ est le nombre $7$, tandis que la séquence $[2, 3, 2, 3]$ ne possède aucun leader.

Dans ce problème, nous nous concentrerons sur cette seconde définition du mot « leader ». Étant donné une séquence de nombres, votre tâche est de la diviser en un nombre minimal de sous-séquences (pas nécessairement contiguës), dont chacune possède un leader, et d'afficher ce nombre minimal. On peut démontrer qu'une telle partition est toujours possible.

Entrée

La première ligne de l'entrée contient un entier $n$ ($1 \le n \le 500\,000$), représentant la longueur de la séquence.

La deuxième ligne de l'entrée contient une séquence de $n$ entiers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

Sortie

La seule ligne de sortie doit contenir un entier représentant le nombre minimal possible de sous-séquences en lesquelles la séquence d'entrée peut être divisée, de telle sorte que chaque sous-séquence résultante possède un leader.

Exemples

Entrée 1

5
1 2 3 1 2

Sortie 1

2

Remarque

La séquence d'entrée peut être divisée, par exemple, en sous-séquences $[1, 3, 1]$ et $[2, 2]$. De cette façon, les deux sous-séquences résultantes possèdent un leader (respectivement les nombres $1$ et $2$).