2317. [Codeforces 675E] 死神永生

【题目描述】

在很多很多很多很多很多年以前，宇宙是十维的，那是一个无法想象，不可描述的世界。

然而，宇宙间的文明互相猜忌，他们疯狂地进行降维打击，最后，宇宙变成了一维。

在这条直线上，有着若干个地铁站$1,2,3.......,n$生命是什么呢？一个原点。直线的尽头是什么呢,是地铁站$n$,传说中存在一位带着眼镜的年老的两栖类生物.这使得$1,2,3,....n-1$的地铁站的生命体去$n$号地铁站朝圣。每个地铁站（除了$n$号）都有一个参数$a_i$,表示$i$号地铁站能买到目的地为$i+1$到$a_i$号地铁站的车票，每张车票1元。有些生命表示，即便见不到长者，朝着长者的方向走一走也是极好的，所以你需要计算,$\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}p(i,j)$,$p(i,j)$表示i号地铁站到j号地铁站所需要的最少花费.

【输入格式】

第一行一个整数$n$

接下来$n-1$个数，表示$a_i$

【输出格式】

只有一个整数$ans$

【样例输入】

5
2 3 5 5

【样例输出】

17

【提示】

$p(1, 2) = 1$ 

$p(1, 3) = 2$ 

$p(1, 4) = 3$ 

$p(1, 5) = 3$ 

$p(2, 3) = 1$ 

$p(2, 4) = 2$ 

$p(2, 5) = 2$ 

$p(3, 4) = 1$ 

$p(3, 5) = 1$ 

$p(4, 5) = 1$

数据范围：

对于30%的数据$N<=2000$

对于60%的数据$N<=100000$,数据随机

对于100%的数据$N<=100000$

【来源】

CF 675E