Element Majoritari X61571

Statement

Donat un conjunt de $n$ números diem que un número és l’element majoritari si apareix més de $\frac{n}{2}$ vegades. Donat un conjunt de números, digueu si hi ha element majoritari, en cas que n’hi hagi indiqueu quin és.

Entrada

L’entrada consisteix en diversos casos, hi ha com a molt $200$ casos. Cada cas consta de dues línies, la primera conté un enter $1 \leq n \leq 10^5$ , la mida del conjunt. La segona línia conté els $n$ números del conjunt, $a_i$ amb $1 \leq a_i \leq 10^9$ . La suma de la mida de tots els conjunts és menor que $5\cdot10^5$ .

Sortida

Escriviu un enter per línia: l’element majoritari. En cas que no existeixi tal element escriviu "Sense solucio".

Public test cases

Input

8
3 3 3 4 4 4 4 4 
6
1 1 2 1 1 2
6
1 2 3 4 5 6
4
1 1 2 2
5
1 1 1 2 2

Output

4
1
Sense solucio
Sense solucio
1

Information

Author: Max Balsells
Language: Catalan
Official solutions: C++
User solutions: C++