A10426 | 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$ .