bvarcolaci

Se pare că toate ideile mari care sau î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 și precizări

• 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

bvarcolaci.in

6
1 2 1 2 3 2

bvarcolaci.out

10 

Explicație

Fiecare subsecvență de câte un element are element majoritar.

Celelalte subsecvențe sunt:
1 2 1 2 3 2
1 2 1 2 3 2
1 2 1 2 3 2
1 2 1 2 3 2