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

Input

The first line of the input contains a single integer $*n*$ ($2 ≤ *n* ≤ 100 000$) — 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.

Output

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

Note

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