Modiana

Límite de tiempo

1000 ms

Límite de memoria

128 MiB

Dado un arreglo de tamaño $n$, encuentra su «modiana». La diferencia con la mediana normal es que la «modiana» es el entero que se encuentra en el medio si ordenamos a todos los números del arreglo por su frecuencia (la cantidad de veces que aparece el entero en el arreglo) y en caso de empate lo ordenamos por su valor.

Para ser precisos, el índice del medio de un array $a_1,a_2,\dots ,a_n$ es $\lfloor (n+1)/2\rfloor$.

Entrada

La primera linea contiene un entero $n$ ($1\le n\le {10}^5$).

La segunda línea contiene $n$ enteros $a_1,a_2,\dots ,a_n$ ($1\le a_i\le n$).

Salida

Imprime un solo entero que represente la «modiana».

Ejemplo

Entrada

5
1 3 4 2 2

Salida

4

Entrada

6
5 3 3 2 2 2

Salida

3

Notas