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