Según el diccionario PWN, un "líder" es, entre otras cosas, "el dirigente de un partido político, un sindicato u otras organizaciones sociales". Sin embargo, en algoritmia, llamamos líder de una secuencia de elementos a aquel elemento cuyo número de apariciones es estrictamente mayor que la mitad de la longitud de la secuencia. Por ejemplo, el líder de la secuencia $[7, 2, 5, 7, 7]$ es el número $7$, mientras que la secuencia $[2, 3, 2, 3]$ no tiene líder en absoluto.

En este problema nos centraremos en el segundo significado de la palabra "líder". Dada una secuencia de números, tu tarea es dividirla en el número mínimo de secuencias (no necesariamente contiguas), cada una de las cuales posea un líder, e imprimir dicho número mínimo. Se puede demostrar que tal división siempre es posible.

Entrada

La primera línea de la entrada contiene un número entero $n$ ($1 \le n \le 500\,000$), que representa la longitud de la secuencia.

La segunda línea de la entrada contiene una secuencia de $n$ números enteros $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

Salida

En la única línea de salida debe aparecer un número entero que represente el número mínimo posible de secuencias en las que se puede dividir la secuencia de entrada de modo que cada secuencia resultante posea un líder.

Ejemplos

Entrada 1

5
1 2 3 1 2

Salida 1

2

Nota

La secuencia de entrada se puede dividir, por ejemplo, en las secuencias $[1, 3, 1]$ y $[2, 2]$. De esta manera, ambas secuencias resultantes tendrán un líder (los números $1$ y $2$, respectivamente).