记录编号	261447	评测结果	AAAAAAAAAA
题目名称	[Codeforces 675E] 死神永生	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	0.323 s
提交时间	2016-05-17 17:37:12	内存使用	4.51 MiB

#include <fstream>
#include <algorithm>
#include <cstring>
#define N 100010
using namespace std;
typedef long long ll;
ifstream cin("history_of_earth.in");
ofstream cout("history_of_earth.out");
int INF=(1<<28);
int n;
int a[N]={0};
ll DP[N]={0};
class node
{
public:
	int val,pos;
	node()
	{
		val=-INF;
		pos=0;
	}
	void make(int a,int b)
	{
		val=a;
		pos=b;
	}
	bool operator <(node a)
	{
		if(val==a.val)return pos>a.pos;
		return val<a.val;
	}
	void print()
	{
		cout<<val<<' '<<pos<<endl;
	}
};
node operator +(node a,node b)
{
	if(a<b)a=b;
	return a;
}
class rangetree
{
public:
	node seg[4*N];
	void pushup(int o)
	{
		seg[o]=seg[o<<1]+seg[o<<1|1];
	}
	void modify(int o,int l,int r,int val,int x)
	{
		if(l==r)
		{
			seg[o].make(val,x);
			return ;
		}
		int mid=(l+r)>>1;
		if(x<=mid)modify(o<<1,l,mid,val,x);
		else modify(o<<1|1,mid+1,r,val,x);
		pushup(o);
	}
	node query(int o,int l,int r,int ql,int qr)
	{
		if(ql<=l&&r<=qr)return seg[o];
		int mid=(l+r)>>1;
		node ans;
		if(ql<=mid)ans=ans+query(o<<1,l,mid,ql,qr);
		if(mid<qr)ans=ans+query(o<<1|1,mid+1,r,ql,qr);
		return ans;
	}
}A;
void read()
{
	int i;
	cin>>n;
	for(i=1;i<n;i++)cin>>a[i];
	a[n]=n;
	for(i=1;i<=n;i++)A.modify(1,1,n,a[i],i);
}
void work()
{
	int i,u;
	node S;
	ll ans=0;
	DP[n]=0;
	for(i=n-1;i>=1;i--)
	{
		S=A.query(1,1,n,i+1,a[i]);
		u=S.pos;
		DP[i]=DP[u]+n-i-(a[i]-u);
	}
	for(i=1;i<=n;i++)ans+=DP[i];
	cout<<ans<<endl;
}
int main()
{
	read();
	work();
	return 0;
}