Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | mate.in, mate.out | Sursă | Lot Bistrita 2009, Baraj 3 |
| Autor | Adrian Airinei | Adăugată de |  Andrei-Bogdan Antonescu •andrei-alpha |
| Timp execuţie pe test | 0.425 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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 ).
Cerinta
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
- 1 ≤ N ≤ 500.000
- 1 ≤ Si ≤ N
Exemplu
| mate.in | mate.out |
|---|---|
| 5 4 1 1 2 3 | 4 |
