Fişierul intrare/ieşire:	bvarcolaci.in, bvarcolaci.out	Sursă	ONI 2017, clasele 11-12
Autor	Eugenie Daniel Posdarascu	Adăugată de	Bogdan Ciobanu •bciobanu
Timp execuţie pe test	1.5 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Bvarcolaci

"Se pare că toate ideile mari care s­au înscripţionat pe vecie în inima Umanităţii au trebuit să se înfăţişeze lumii întâi cu măşti monstruoase şi terifiante."

_{(Friedrich Nietzsche)}

Se dă un vector cu N elemente. Să se precizeze câte subsecvenţe ale acestuia admit element majoritar.

Date de intrare

Fişierul bvarcolaci.in conţine pe prima linie numărul natural N, iar pe a doua linie cele N elemente ale vectorului, separate prin câte un spaţiu.

Date de ieşire

Fişierul bvarcolaci.out va conţine pe prima linie numărul subsecvenţelor care admit element majoritar.

Restricţii

• 1 ≤ N ≤ 250.000
• Toate valorile din vector sunt cuprinse între 1 şi N
• O subsecvenţă este un subşir de elemente care apar pe poziţii consecutive în şirul iniţial. Subsecvenţele sunt definite unic de indicii primului şi ultimului element din subsecvenţă în şirul initial.
• O valoare este element majoritar al unui vector cu K elemente dacă apare de cel puţin [K/2]+1 ori în vector, unde prin [x] am notat partea întreagă a lui x.

Exemplu

Cum se trimit solutii?