| Fişierul intrare/ieşire: | jolteon.in, jolteon.out | Sursă | Lot Seniori Alexandria, 2017, baraj 6 |
| Autor | Adrian Budau, Teodor Ionescu | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 4 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | jolteon.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]
