题目链接：这里
题意：你可以从第i个城市买的从i到[i+1,a[i]]的车票，现在Pij表示从i到j的最小车票花费。现在让你求sigma p[i][j]。
解法：CF题解。

首先我们理解一下为什么是取这个m，显然出题人的意思是dp[i]是要从这个a[m]最大上面去继承答案。我们简单画一下图就能发现这样一个大小关系： i<m<a[i]<a[m]<n。 这个n-i显然是表示i+1~n每个站至少买一次票，那么哪些站多买了呢？m+1~a[i]这些站，因为之前m到这些站就买了一次票，这一次再买就重复了，于是就有-(a[i]-m)。那么怎么能保证a[i]+1~n的每一站是买的最少的票呢？那么就直接继承dp[m]中最小的买票次数就行啦。

//CF 675E

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+7;
int n, a[maxn];
long long dp[maxn];
int ans[maxn*4];
inline void pushup(int o){
    if(a[ans[o*2]] > a[ans[o*2+1]]) ans[o] = ans[o*2];
    else ans[o] = ans[o*2+1];
}
void build(int l, int r, int o){
    if(l == r){
        ans[o] = l;
        return ;
    }
    int m = (l + r) / 2;
    build(l, m, o*2);
    build(m+1, r, o*2+1);
    pushup(o);
}
int query(int L, int R, int l, int r, int o){
    if(L <= l && r <= R) return ans[o];
    int m = (l + r) / 2;
    if(R <= m) return query(L, R, l, m, o*2);
    else if(L > m) return query(L, R, m+1, r, o*2+1);
    else{
        int x1 = query(L, m, l, m, o*2);
        int y1 = query(m+1, R, m+1, r, o*2+1);
        if(a[x1] > a[y1]) return x1;
        else return y1;
    }
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n - 1; i++) scanf("%d", &a[i]); a[n] = n-1;
    build(1, n, 1);
    long long ans = 0;
    dp[n] = 0;
    for(int i = n - 1; i >= 1; i--){
        int temp = query(i+1, a[i], 1, n, 1);
        dp[i] = dp[temp] + 1LL*(n-i-(a[i]-temp));
        ans = ans + dp[i];
    }
    printf("%lld\n", ans);
    return 0;
}