== include(page="template/taskheader" task_id="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 [(L+1)/2]ori (partea întreagă a lui (L+1)/2).

==include(page="template/badtests")==
 
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 $[(L+1)/2]$ ori (partea întreagă a lui $(L+1)/2$ ).

h2. Cerinta

h2. 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.

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.

h2. Date de ieşire

h2. Restricţii

* $1 ≤ N ≤ 500.000$
* $1 ≤ Si ≤ N$

* $1 ≤ N ≤ 500.000$
* $1 ≤ S{~i~} ≤ N$

h2. Exemplu

4163