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