Sirbun

sirbun

== include(page="template/taskheader" task_id="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 Ai din şir şi un număr natural x şi se scade x din Ai, deci Ai devine Ai − 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.
 
h2. 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.

Poveste şi cerinţă...

h2. 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.

Fişierul de intrare $sirbun.in$ ...

h2. 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.

În fişierul de ieşire $sirbun.out$ ...

h2. Restricţii

* $1 ≤ N ≤ 100 000$
* $1 ≤ A{~i~} ≤ N$
 
table(subtasks). |_. # |_. Punctaj |_. Restrcţii |
| 1 | 19 | $1 ≤ N ≤ 300$ |
| 2 | 20 | $1 ≤ N ≤ 1500$ |
| 3 | 22 | $1 ≤ N ≤ 7000$ |
| 4 | 17 | $1 ≤ N ≤ 50 000$ |
| 5 | 22 | Restricţiile iniţiale |

* $... ≤ ... ≤ ...$

h2. Exemplu