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ă:

1. Numărul $x$ nu apare în subsecvență, sau
2. 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.

Implementare

Programul vostru va trebui să implementeze următoarea funcție:

long long solve(int N, int* V);

Această funcție este apelată o singură dată. Parametrul $N$ reprezintă numărul de elemente ale șirului. Parametrul $V$ este un array de lungime $N$, indexat de la 0, care conține elementele șirului $V$. Această funcție trebuie să returneze numărul de subsecvențe electrizante pe care le conține șirul $V$.

Testare

Pentru a vă testa local soluțiile, vă oferim programul main.cpp și header-ul jolteon.h. Programul main.cpp citește din fișierul de intrare jolteon.in, apelează funcția solve a concurentului și afișează răspunsul returnat de aceasta.

Pe prima linie a fișierului jolteon.in se află numărul natural N. Pe a doua linie se află N numere naturale, reprezentând elementele array-ului $V$. Pe singura linie a fișierului jolteon.out se află răspunsul returnat de funcția solve.

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

4
2 2 2 3

jolteon.out

7

Explicație

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