说明

在一条长长的火车路旁分布了 $n$ 个火车站，在第 $i$ 个火车站只能购买从$i + 1$ 到$a_{i}$火车站的票，最后一个站不能买票.

设$\rho _{i,j}$为从$i$站到$j$站需要购买的最少车票数量,要求你计算所有对$1\leqslant i\leqslant j\leqslant n$中所有值 $\rho _{i,j}$的总和。

输入格式

第一行一个正整数$n$

第二行$n-1$个正整数 $a_{i}$,其中第$i$个表示在第$i$个车站可以购买从$i + 1$到$a_{i}$的每个车站的车票.

输出格式

一行一个数，所有$1\leqslant i\leqslant j\leqslant n$对$\rho _{i,j}$的总和

样例

5
2 3 5 5

17

4
4 4 4

6

样例解释

样例 1：

$\rho _{1,2}=1$

$\rho _{1,3}=2$

$\rho _{1,4}=3$

$\rho _{1,5}=3$

$\rho _{2,3}=1$

$\rho _{2,4}=2$

$\rho _{2,5}=2$

$\rho _{3,4}=1$

$\rho _{3,5}=1$

$\rho _{4,5}=1$

综上共买: 1+2+3+3+1+2+2+1+1+1=17 次

数据范围

• 对于 30%的数据，$1\leqslant n\leqslant 100$ -对于 100%的数据， $1\leqslant n\leqslant 10^{5},i+1\leqslant a_{i}\leqslant n$

来源

Codeforces 675E