#include <fstream>
#define maxn 5000100

using namespace std;

ifstream in("deque.in");
ofstream out("deque.out");
long i,n,k,e,v,a[maxn],d[maxn];
long long sum;

int main()
{
  in >> n;
  for (i=1;i<=n;++i) in >> a[i];
  
  for (i=1;i<=n;++i){
	while (e<=v && d[i]<=a[d[v]]) --v;
	
	if (d[e]==i-k) ++e;
	
	if (i>=k) sum+=d[e];	  
	  
  }	
  
  out << sum;
  
  in.close();
  out.close();
	
	
  return 0;	
}