Fişierul intrare/ieşire:jolteon.in, jolteon.outSursăLot Seniori Alexandria, 2017, baraj 6
AutorAdrian Budau, Teodor IonescuAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test8 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Jolteon

Spark, liderul echipei Instinct, i-a făcut cadou Jolteonului său un şir V de lungime N. Jolteon se joacă cu acest şir, alegându-şi câte o subsecvenţă şi uitându-se adânc la ea. Fiind un pokemon care detestă neutralitatea, el defineşte o subsecvenţă ca fiind electrizantă dacă, pentru fiecare număr natural x, una dintre aceste condiţii este validă:

  • Numărul x nu apare în subsecvenţă, sau
  • Numărul x apare de un număr impar de ori în subsecvenţă.

Ajutaţi-l pe Jolteon să determine câte subsecvenţe electrizante are şirul pe care l-a primit.

Date de intrare

Pe primul rând al fişierului de intrare jolteon.in va conţine numărul N.
Următorul rând va conţine şirul V, elementele sale fiind separate de spaţii.

Date de ieşire

Fişierul de ieşire jolteon.out va conţine valoarea cerută.

Restricţii şi precizări

  • 1 ≤ N ≤ 100.000
  • 1 ≤ V[i] ≤ 1.000.000
  • Pentru 20% din teste, N ≤ 1.000
  • Prin subsecvenţă se înţelege o succesiune de unul sau mai multe elemente aflate pe poziţii consecutive în şirul iniţial.

Exemplu

jolteon.injolteon.out
4
2 2 2 3
7

Explicaţie

Subsecvenţele electrizante sunt:
[1, 1], [1, 3], [1, 4], [2, 2], [3, 3], [3, 4], [4, 4]

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?