Fişierul intrare/ieşire:	sirbun.in, sirbun.out	Sursă	ONI 2023, Baraj Seniori, ziua 1
Autor	Mihai Bunget	Adăugată de	Livia Magureanu •livlivi
Timp execuţie pe test	0.2 sec	Limită de memorie	524288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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 sirbun.in se află numărul N, iar pe a doua linie elementele şirului A.

Date de ieşire

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

Restricţii

• 1 ≤ N ≤ 100 000
• 1 ≤ A_i ≤ N

Exemplu

Explicaţie

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}

Cum se trimit solutii?