#include <bits/stdc++.h>

using namespace std;

ifstream in("numarare.in");
ofstream out("numarare.out");

int v[1000005],z[1000005];
long long ans=0;
int main()
{
	int n;
	in>>n;
	for(int i=1;i<=n;i++)
		in>>v[i];
	int R=0,C=0;
	for(int i=1;i<n;i++)
	{
		int aux=2*C-i;
		if(i>R || z[aux]>=R-i)
		{
			if(i>R) R=i;
			int k=R+1;
			while(k<=n && (2*i-k+1>0))
				k++;
			k--;
			z[i]=k-i;
			if(k>R)
			{
				C=i;
				R=k;
			}
		}
		else z[i]=z[aux];
		ans+=z[i];
	}
	out<<ans;
	return 0;
}