CF675E.Trains and Statistic

Vasya commutes by train every day. There are $n$ train stations in the city, and at the $i$ -th station it's possible to buy only tickets to stations from $i+1$ to $a_{i}$ inclusive. No tickets are sold at the last station.

Let $ρ_{i,j}$ be the minimum number of tickets one needs to buy in order to get from stations $i$ to station $j$ . As Vasya is fond of different useless statistic he asks you to compute the sum of all values $ρ_{i,j}$ among all pairs 1<=i<j<=n .

The first line of the input contains a single integer $n$ ( $2<=n<=100000$ ) — the number of stations.

The second line contains $n-1$ integer $a_{i}$ ( $i+1<=a_{i}<=n$ ), the $i$ -th of them means that at the $i$ -th station one may buy tickets to each station from $i+1$ to $a_{i}$ inclusive.

Print the sum of $ρ_{i,j}$ among all pairs of 1<=i<j<=n .

In the first sample it's possible to get from any station to any other (with greater index) using only one ticket. The total number of pairs is $6$ , so the answer is also $6$ .

Consider the second sample:

• $ρ_{1,2}=1$
• $ρ_{1,3}=2$
• $ρ_{1,4}=3$
• $ρ_{1,5}=3$
• $ρ_{2,3}=1$
• $ρ_{2,4}=2$
• $ρ_{2,5}=2$
• $ρ_{3,4}=1$
• $ρ_{3,5}=1$
• $ρ_{4,5}=1$

Thus the answer equals $1+2+3+3+1+2+2+1+1+1=17$ .