sirbun

Un străbun get, Ziraxes, le-a dat dacilor liberi să rezolve o problemă de programare, aceasta fiind o activitate mai plăcută decât să care bolovani, pietricele şi nisip. Legenda spune că asupra elementelor unui şir $A$ de numere naturale nenule se poate efectua următoarea operaţie:

• Se alege un element $A_{i}$ din şir şi un număr natural $x$ şi se scade $x$ din $A_{i}$, deci $A_{i}$ devine $A_{i}-x$.

Şirul $A$ se numeşte bun dacă aplicând operaţia de oricâte ori, elementele şirului $A$ devin numere naturale nenule distincte. De exemplu, şirul $2,3,3,5$ este bun deoarece scăzând $2$ din al doilea element el devine $2,1,3,5$ şi are elementele distincte, iar şirul $2,2,7,2,4$ nu este bun.

Cerință

Fiind dat un şir $A$ format cu $N$ elemente numere naturale nenule, determinaţi numărul subsecvenţelor din şir care sunt şiruri bune. O subsecvenţă a șirului este formată din elemente din şir aflate pe poziţii consecutive.

Date de intrare

Pe prima linie a fişierului de intrare se află numărul $N$, iar pe a doua linie elementele şirului $A$.

Date de ieșire

În fişierul de ieşire se va afişa numărul subsecvenţelor din şirul $A$ care sunt şiruri bune.

Restricții

• $1\leq N \leq 100\ 000$.
• $1\leq A_{i} \leq N$.

Exemplu

sirbun.in

5
4 2 2 3 2

sirbun.out

13

Subsecvenţele bune sunt:

1. $\{4\}$
2. $\{2\}$
3. $\{2\}$
4. $\{3\}$
5. $\{2\}$
6. $\{4,2\}$
7. $\{4,2,2\}$
8. $\{4,2,2,3\}$
9. $\{2,2\}$
10. $\{2,2,3\}$
11. $\{2,3\}$
12. $\{2,3,2\}$
13. $\{3,2\}$