mate

Mirunel, fratele Mirunei, a dezvoltat o adevarată pasiune pentru matematică. Jucându-se cu şiruri de numere naturale, a întalnit o problemă pentru care abilităţile sale de matematician nu sunt suficiente. El a descoperit un şir $S$ format din $N$ numere naturale cuprinse între $1$ şi $N$ şi trebuie să determine lungimea cea mai mare a unei subsecvenţe care conţine un element majoritar. Într-o subsecvenţă de lungime $L$, un element este majoritar dacă apare de cel puţin $\lfloor \frac{L+1}{2} \rfloor$ ori (partea întreagă a lui $\frac{L+1}{2}$).

Cerinţă

Determinaţi lungimea maximă a unei subsecvenţe care conţine un element majoritar.

Date de intrare

Fişierul de intrare mate.in va conţine pe prima linie un singur număr natural, $N$, având semnificaţia din enunţ. Pe urmatoarea linie se află $N$ numere naturale separate printr-un singur spaţiu, reprezentând şirul de numere.

Date de ieșire

Fişierul de ieşire mate.out va conţine un singur număr natural, reprezentând lungimea maximă a unei subsecvenţe care conţine un element majoritar.

Restricții și precizări

• $1 \leq N \leq 500 \ 000$
• $1 \leq S_i \leq N$

Exemplul 1

mate.in

5
4 1 1 2 3

mate.out

4

Explicație

Subsecvenţa $1 \ 1 \ 2 \ 3$ de lungime $4$ îl conţine pe $1$, care este element majoritar deoarece apare de $\lfloor \frac{4+1}{2} \rfloor = 2$ ori.