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.

瓦西里每天乘火车通勤。这座城市共有 $n$ 个火车站，在第 $i$ 个车站，仅可购买前往编号从 $i+1$ 到 $a_i$（含端点）的各车站的车票。最后一个车站不售任何车票。

令 $\rho_{i,j}$ 表示从第 $i$ 站到达第 $j$ 站所需购买的最少车票数。由于瓦西里热衷于各种无用的统计量，他请你计算所有满足 $1 \le i < j \le n$ 的数对 $(i,j)$ 对应的 $\rho_{i,j}$ 值之和。

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.

输入的第一行包含一个整数 $n$（$2 \leq n \leq 100\,000$）—— 表示车站的数量。

第二行包含 $n-1$ 个整数 $a_i$（$i+1 \leq a_i \leq n$），其中第 $i$ 个数表示：在第 $i$ 个车站，可以购买前往从第 $i+1$ 站到第 $a_i$ 站（含端点）的所有车站的车票。

Print the sum of ρ_i_, j among all pairs of 1 ≤ i < j ≤ n.

输出所有满足 $1 \le i < j \le n$ 的数对 $(i, j)$ 对应的 $\rho_{i,j}$ 之和。

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.

在第一个样例中，可以仅使用一张车票从任意车站到达任意编号更大的车站。总共有 6 对车站，因此答案也是 6。

考虑第二个样例：

• ρ₁,₂ = 1
• ρ₁,₃ = 2
• ρ₁,₄ = 3
• ρ₁,₅ = 3
• ρ₂,₃ = 1
• ρ₂,₄ = 2
• ρ₂,₅ = 2
• ρ₃,₄ = 1
• ρ₃,₅ = 1
• ρ₄,₅ = 1

因此答案等于 1 + 2 + 3 + 3 + 1 + 2 + 2 + 1 + 1 + 1 = 17。