← 返回题目列表

Codeforces · 675/E

E. 火车和统计

中文机器翻译题面 查看原题

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。