== include(page="template/taskheader" task_id="mate") ==

==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$ ).

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. Restricţii
* $1 ≤ N ≤ 500.000$

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

* $1 ≤ Si ≤ N$

h2. Exemplu

4163