Trains and Statistic

题意翻译

有n个车站，告诉你第i个车站可以到[ i+1，a[i] ]。 若p[i][j]为从i到j最小车票花费，求所有p[i][j]的和 输入 第一行n。 第二行n-1个数，表示a[i]. 输出 见上（1 ≤ i < j ≤ n)

题目描述

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&lt;j<=n $ .

输入输出格式

输入格式

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

输出格式

Print the sum of $ ρ_{i,j} $ among all pairs of $ 1<=i&lt;j<=n $ .

输入输出样例

输入样例 #1

4
4 4 4

输出样例 #1

6

输入样例 #2

5
2 3 5 5

输出样例 #2

17

说明

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

题意翻译

有n个车站，告诉你第i个车站可以到[ i+1，a[i] ]。 若p[i][j]为从i到j最小车票花费，求所有p[i][j]的和 输入 第一行n。 第二行n-1个数，表示a[i]. 输出 见上（1 ≤ i < j ≤ n)