列车与统计

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

有 $n$ 个火车站从左到右编号为 $1,2,\ldots,n$。

从第 $i$ 个站（$i<n$）花费 $1$ 元，可以到达任意满足 $i+1\le j\le a_i$ 的站 $j$。

对 $i<j$，记 $\rho_{i,j}$ 为从站 $i$ 到站 $j$ 的最小花费。求

输入格式

第一行包含一个整数 $n$。

第二行包含 $n-1$ 个整数 $a_1,a_2,\ldots,a_{n-1}$。

输出格式

输出一个整数，表示所有有序站对最小花费之和。

样例输入 1

4
4 4 4

样例输出 1

6

样例输入 2

5
2 3 5 5

样例输出 2

17

数据范围

• $1\le n\le10^5$；
• 对每个 $1\le i<n$，有 $i+1\le a_i\le n$。

本题采用独立测试点计分。