贪心，递推，线段树，$RMQ$。
假设我们记$ans[i]$是以$i$点为起点对答案的贡献，那么答案就是$\sum\limits_{i = 1}^n {ans[i]}$。
$ans[i]$怎么计算呢？
首先，$[i+1,a[i]]$区间上肯定都是$1$（即上图紫线）。
然后在$[i+1,a[i]]$上找到一个$tmp$，使得$tmp$点能够达到的最右端是$[i+1,a[i]]$中最大的，那么$[a[i]+1,a[tmp]]$肯定都是2（即上图绿线）。
然后在$[a[i]+1,a[tmp]]$找一个$tmp2$......依次下去，计算出以$i$为起点对答案的贡献。
但是这样做复杂度太高，需要进行优化。
如果我们知道了$ans[tmp]$，那么就可以$O(1)$知道$ans[i]$，递推一下就可以了。
反过来想，如果我们想知道$ans[i]$，也就是要找到$tmp$，然后从$ans[tmp]$转移过来。
找$tmp$的话可以用线段树，也可以用$RMQ$预处理一下。
$RMQ$：
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0),eps=1e-;
void File()
{
freopen("D:\\in.txt","r",stdin);
freopen("D:\\out.txt","w",stdout);
}
template <class T>
inline void read(T &x)
{
char c=getchar(); x=;
while(!isdigit(c)) c=getchar();
while(isdigit(c)) {x=x*+c-''; c=getchar();}
} const int maxn=;
int a[maxn],n,tmp,dp[maxn][];
LL ans[maxn]; void RMQ_init()
{
for(int i=;i<n;i++) dp[i][]=i;
for(int j=;(<<j)<=n;j++)
for(int i=;i+(<<j)-<n;i++){
if(a[dp[i][j-]]>a[dp[i+(<<(j-))][j-]]) dp[i][j]=dp[i][j-];
else dp[i][j]=dp[i+(<<(j-))][j-];
}
} int RMQ(int L,int R)
{
int k=;
while((<<(k+))<=R-L+) k++;
if(a[dp[L][k]]>a[dp[R-(<<k)+][k]]) return dp[L][k];
return dp[R-(<<k)+][k];
} int main()
{
scanf("%d",&n);
for(int i=;i<n-;i++) scanf("%d",&a[i]),a[i]--;
a[n-]=n-; RMQ_init(); ans[n-]=; LL d=;
for(int i=n-;i>=;i--)
{
tmp=RMQ(i+,a[i]);
ans[i]=ans[tmp]-(a[i]-tmp)+n--a[i]+a[i]-i;
d=d+ans[i];
}
printf("%lld\n",d);
return ;
}
线段树：
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0),eps=1e-;
void File()
{
freopen("D:\\in.txt","r",stdin);
freopen("D:\\out.txt","w",stdout);
}
template <class T>
inline void read(T &x)
{
char c=getchar(); x=;
while(!isdigit(c)) c=getchar();
while(isdigit(c)) {x=x*+c-''; c=getchar();}
} const int maxn=;
int a[maxn],n,s[*maxn],M,tmp;
LL ans[maxn]; void build(int l,int r,int rt)
{
if(l==r) { s[rt]=a[l]; return; }
int m=(l+r)/; build(l,m,*rt); build(m+,r,*rt+);
s[rt]=max(s[*rt],s[*rt+]);
} void f(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R) { M=max(M,s[rt]); return; }
int m=(l+r)/;
if(L<=m) f(L,R,l,m,*rt);
if(R>m) f(L,R,m+,r,*rt+);
} void force(int l,int r,int rt)
{
if(l==r) {tmp=l; return;}
int m=(l+r)/;
if(s[*rt]==M) force(l,m,*rt);
else force(m+,r,*rt+);
} void h(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
if(s[rt]<M) return;
force(l,r,rt); return;
}
int m=(l+r)/;
if(L<=m) h(L,R,l,m,*rt); if(tmp!=-) return;
if(R>m) h(L,R,m+,r,*rt+); if(tmp!=-) return;
} int main()
{
scanf("%d",&n);
for(int i=;i<=n-;i++) scanf("%d",&a[i]); a[n]=n;
build(,n,); ans[n]=; LL d=;
for(int i=n-;i>=;i--)
{
M=tmp=-; f(i+,a[i],,n,); h(i+,a[i],,n,);
ans[i]=ans[tmp]-(a[i]-tmp)+n-a[i]+a[i]-i;
d=d+ans[i];
}
printf("%lld\n",d);
return ;
}