arb2

Cerință

Vraciul Marian dorește să își afle strămoșii. El știe foarte puține lucruri despre ei, în mare parte datorită faptului că tatăl său, vraciul Șerban, era cam secretos, iar singura moștenire pe care i-a lăsat-o a fost un pergament pe care se află un șir $A$ de $N$ numere naturale. El suspectează că arborele său genealogic este cumva codificat acolo, într-o subsecvență a șirului.

El știe că, în trecut, codificarea unui arbore se făcea reținând pentru fiecare nod $i$ numărul său de fii direcți. Astfel, un șir $B$ de lungime $K$ este considerat o codificare validă dacă, considerând $B[i]$ ca fiind numărul de fii direcți ai nodului $i$, se poate construi un arbore valid cu $K$ noduri (etichetate de la $1$ la $K$).

Vraciul Marian se întreabă: câte subsecvențe ale șirului $A$ reprezintă codificarea unui arbore valid?

O subsecvență a șirului $A$ este definită prin doi indici $L$ și $R$ ($1 \leq L \leq R \leq N$) și este formată din elementele contigue $A[L], A[L+1], \dots, A[R]$.

Date de intrare

Pe prima linie se găsește un număr natural, $N$.
Pe următoarea linie se găsesc cele $N$ numere naturale ale șirului $A$.

Date de ieșire

Pe prima linie se va găsi un singur număr întreg, reprezentând numărul de subsecvențe valide ale șirului $A$.

Restricții și precizări

• $1 \leq N \leq 500 \ 000$;
• $0 \leq A[i] \leq 1 \ 000 \ 000 \ 000$;
• Pentru teste în valoare de 15 puncte, $N \leq 10$;
• Pentru alte teste în valoare de 35 de puncte, $N \leq 1000$;

Exemplul 1

stdin

3
0 2 0

stdout

3

Explicație

Subsecvențele valide sunt:

• $(1, 1)$
• $(3, 3)$
• $(1, 3)$
  În total există $3$ subsecvențe valide.

Exemplul 2

stdin

3
1 1 1

stdout

0

Explicație