Pătrate frecvente

Cerință

Aciup are prea multe restanțe, așa că a decis să înceapă un nou server de Minecraft. Pentru acesta el are o strategie foarte bine pusă la punct, bazată pe căutarea materialelor prețioase. Fiecare item din joc are un cod între $1$ și $500\,000$, iar Aciup a notat codurile celor $N$ iteme găsite până acum în ordinea în care le-a găsit.
Deoarece dorește să își mărească semnificativ cantitatea de materiale prețioase, el alege la întamplare o subsecvență și numară câte bucăți are din fiecare material și le ordonează crescător. Aciup se declară mulțumit dacă cea mai mică frecvență este $1$ (graba strică treaba), iar următoarele sunt, pe rând, $4,9,16,\dots,k^2$.
Frecvențele trebuie să fie unice și să reprezinte șirul pătratelor perfecte începând cu $1$. Aciup nu are timp să calculeze, dat fiind că trebuie să învețe, așa că va roagă pe voi să îl ajutați să numere câte astfel de subsecvențe sunt mulțumitoare.
O subsecvență a șirului A este definită prin $2$ indici $L$ și $R$ ($1 \leq L \leq R \leq N$) și este formată din elemenele contigue $A[L], A[L+1],..., A[R]$.

Date de intrare

Pe prima linie din input se găsește $N$, numărul de iteme găsite de Aciup, iar pe a doua linie se găsesc $N$ numere cu proprietatea din enunț.

Date de ieșire

Pe o linie se va afișa numărul de subsecvențe mulțumitoare.

Restricții și precizări

• $1 \leq N \leq 500 \ 000$;
• $1 \leq A[i] \leq 500 \ 000$, pentru $1 \leq i \leq N$;
• Pentru teste în valoare de $15$ puncte, $N \leq 100$.
• Pentru teste în valoare de alte $25$ puncte, $N \leq 1000$.
• Pentru teste în valoare de alte $25$ puncte, $N \leq 50000$.

Exemplul 1

stdin

5
1 1 1 1 2

stdout

6

Explicație

Șirul are 5 elemente. Orice element luat individual formează o subsecvență cu frecvența 1 ($1^2$), rezultând 5 astfel de subsecvențe. De asemenea, subsecvența formată din întregul șir are elementul 2 cu frecvența 1 și elementul 1 cu frecvența 4 ($2^2$). În total avem $5 + 1 = 6$ subsecvențe mulțumitoare.

Exemplul 2

stdin

9
1 1 1 1 2 3 3 3 3

stdout

11

Explicație

Șirul are 9 elemente. Cele 9 elemente luate individual reprezintă 9 subsecvențe cu frecvența 1. Pe lângă acestea, există 2 subsecvențe de lungime 5 cu frecvențele 1 și 4: prima de la indicele 1 la 5 (1 1 1 1 2), și a doua de la indicele 5 la 9 (2 3 3 3 3). În total avem $9 + 2 = 11$ subsecvențe mulțumitoare.