En un arreglo de \(n\) enteros, el elemento mayoritario es el que aparece más de \(\lfloor n / 2 \rfloor\) veces. Se garantiza que existe; encuéntralo.

Seguimiento: ¿puedes resolverlo en tiempo lineal y memoria \(O(1)\)?

Entrada

La primera línea tiene \(n\) \((1 \le n \le 10^5)\) y la segunda los \(n\) enteros \((|a_i| \le 10^9)\).

Salida

El elemento mayoritario.

Ejemplo 1

Entrada

3
3 2 3

Salida

3

Ejemplo 2

Entrada

7
2 2 1 1 1 2 2

Salida

2

Ejemplo 3

Entrada

1
-5

Salida

-5

Basado en el problema 169 de LeetCode, Majority Element, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.