Vasya 每天乘火车上下班。该市有 n 个火车站,在第 i 个车站只能购买从 i + 1 到 ai (含)的车站的车票。末站不卖票。
设 ρi, j 为从 i 站到 j 站需要购买的最少车票数量。由于 Vasya 喜欢不同的无用统计,他要求您计算所有对 1 ≤ i < j ≤ n 中所有值 ρi, j 的总和。
输入
输入的第一行包含一个整数 n (2 ≤ n ≤ 100 000) — 车站数量。
第二行包含n - 1个整数ai(i + 1 ≤ ai ≤ n),其中第i个表示在第i个车站可以购买从i + 1到ai(含)的每个车站的车票。
输出
打印所有 1 ≤ i < j ≤ n 对中 ρi, j 的总和。
示例
输入 #1
4 4 4 4
输出 #1
6
输入 #2
5 2 3 5 5
输出 #2
17
注意
在第一个示例中,可以仅使用一张票从任何车站到达任何其他车站(具有更大的索引)。总对数是 6,所以答案也是 6。
考虑第二个示例:
- ρ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
因此答案等于 1 + 2 + 3 + 3 + 1 + 2 + 2 + 1 + 1 + 1 = 17。