Codeforces Round #353 (Div. 2) E. Trains and Statistic （线段树+dp）

Codeforces Round #353 (Div. 2) E. Trains and Statistic （线段树+dp）

E. Trains and Statistic

time limit per test

memory limit per test

input

output

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 ai

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.

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of stations.

The second line contains n - 1 integer ai (i + 1 ≤ ai ≤ n), the i-th of them means that at the i-th station one may buy tickets to each station from i + 1 to ai

Output

Print the sum of ρi, j among all pairs of 1 ≤ i < j ≤ n.

Examples

input

44 4 4

output

6

input

52 3 5 5

output

17

Note

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, 3ρ1, 4ρ1, 5ρ2, 3ρ2, 4ρ2, 5ρ3, 4ρ3, 5ρ4, 5

Thus the answer equals 1 + 2 + 3 + 3 + 1 + 2 + 2 + 1 + 1 + 1 = 17.

题解：有n个车站,,每个车站都有一个a[i]，从该车站可以花费1的钱到达[ i+1, a[i] ]之间的任意车站,现在让你求d[i][j]的

和的最小值。

设dp[i]表示从i点出发到i+1,i+2,...,n的最小值。那么有dp[i]=dp[m]-(a[i]-m)+n-i，且m是i+1~a[i]之间的数，且a[m]最大

的。因为i < m < a[i] < a[m] < n。所以n-i表示的是 i~n每个站至少买一次票。a[i]-m表示m~a[i]这些站中，m到这些站就

买了一次票，再买一次就重复了，所以要减去重复的。

AC代码：

#pragma comment(linker, "/STACK:102400000,102400000")//#include#include#include#include#include#include#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。