Junaradalla Syrjälästä Helsinkiin on $n$ asemaa, jotka on numeroitu $1, 2, \ldots, n$. Asemalta $i$ voi ostaa lipun mille tahansa asemalle välillä $[i+1, a_i]$. Asemalta $n$ ei voi ostaa mitään lippua. Sanotaan että $d_{i, j}$ on minimimäärä lippuja mitä tarvitsee ostaa matkustaakseen asemalta $i$ asemalle $j$. Tehtävänäsi on laskea $\sum_{i = 1}^{n - 1}{\sum_{j = i + 1}^{n}{d_{i, j}}}$, eli kaikkien $d_{i, j}$ arvojen summa joissa $1 \le i < j \le n$.

Syöte

Syötteen ensimmäisellä rivillä on luku $n$, asemien määrä. Seuraavalla rivillä on $n-1$ lukua, $a_1, a_2, \ldots a_{n-1}$.

Tuloste

Tulosta kaikkien $d_{i, j}$ arvojen summa joissa $1 \le i < j \le n$.

Rajat

• $1 \le n \le 10^5$
• $i+1 \le a_i \le n$

Esimerkki

Syöte:

4
4 4 4

Tuloste:

6

Syöte:

5
2 3 5 5

Tuloste:

17

Tässä testissä $d_{1, 2} =1$, $d_{1, 3} = 2$, $d_{1, 4} = 3$, $d_{1, 5} = 3$, $d_{2, 3} = 1$, $d_{2, 4} = 2$, $d_{2, 5} = 2$, $d_{3, 4} = 1$, $d_{3, 5} = 1$, $d_{4, 5} = 1$