#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 100010
#define ll long long
#define reg register int
#define int long long 

char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline int read() {
	int ans=0, f=1; char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
	return ans*f;
}

int n;
ll a[N];

namespace force{
	ll dp[N];
	inline ll sum(ll k) {return k*(k+1)/2;}
	void solve() {
		memset(dp, 128, sizeof(dp));
		a[0]=-INF; a[n+1]=INF; dp[0]=0;
		for (int i=1; i<=n; ++i) {
			for (int j=0; j<i; ++j) if (a[j]<=a[i]) {
				dp[i]=max(dp[i], dp[j]-sum(i-j-1));
			}
			dp[i]+=a[i];
		}
		for (int i=0; i<=n; ++i) dp[n+1]=max(dp[n+1], dp[i]-sum(n-i));
		printf("%lld\n", dp[n+1]);
		exit(0);
	}
}

namespace task1{
	ll dp[N], l=1, r=0;
	// struct que{double val; int pos; inline void build(double v, int p) {val=v; pos=p;}}q[N];
	int q[N];
	inline ll sum(ll k) {return k*(k+1)/2;}
	inline double calc(ll j, ll k) {return ((2.0*dp[k]-k*k+k)-(2.0*dp[j]-j*j+j))/(1.0*j-k);}
	void solve() {
		memset(dp, 128, sizeof(dp));
		a[0]=-INF; a[n+1]=INF; dp[0]=0;
		q[++r]=0;
		for (int i=1; i<=n; ++i) {
			// while (l<r && a[q[l]]>=a[q[l+1]] && calc(q[l], q[l+1])>=double(2*i)) ++l;
			for (int j=l; j<=r; ++j) if (a[q[j]]<=a[i]) {
				dp[i]=max(dp[i], dp[q[j]]-sum(i-q[j]-1));
			}
			dp[i]+=a[i];
			while (l<r && a[q[r-1]]>=a[q[r]] && calc(q[r-1], q[r])<double(2*i)) {/*cout<<calc(q[r-1], q[r])<<endl;*/ --r;}
			q[++r]=i;
		}
		// cout<<"q: "; for (int i=l; i<=r; ++i) cout<<q[i]<<' '; cout<<endl;
		for (int i=l; i<=r; ++i) dp[n+1]=max(dp[n+1], dp[q[i]]-sum(n-q[i]));
		printf("%lld\n", dp[n+1]);
		exit(0);
	}
}

namespace task{
	ll dp[N];
	int q[N], p[N];
	inline double calc(ll j, ll k) {return ((2.0*dp[k]-k*k-k)-(2.0*dp[j]-j*j-j))/(1.0*j-k);}
	inline bool cmp1(int i, int j) {return a[i]<a[j];}
	inline ll sum(ll k) {return k*(k+1)/2;}
	void cdq(int l, int r) {
		// cout<<"cdq: "<<l<<' '<<r<<endl;
		if (l==r) {dp[p[l]]+=a[p[l]]; return ;}
		int mid=(l+r)>>1, ql=1, qr=0;
		cdq(l, mid);
		sort(p+l, p+mid+1); sort(p+mid+1, p+r+1);
		// cout<<"sort: "<<l<<' '<<r<<endl;
		// cout<<"p: "; for (int i=l; i<=r; ++i) cout<<p[i]<<' '; cout<<endl;
		// cout<<"a: "; for (int i=l; i<=r; ++i) cout<<a[p[i]]<<' '; cout<<endl;
		// cout<<"q: "; for (int i=ql; i<=qr; ++i) cout<<q[i]<<' '; cout<<endl;
		for (int i=mid+1,pos1=l; i<=r; ++i) {
			// cout<<"calc: "<<p[i]<<' '<<q[ql]<<' '<<q[ql+1]<<' '<<calc(q[ql], q[ql+1])<<' '<<2*p[i]<<endl;
			while (pos1<=mid && p[pos1]<p[i]) {
				while (ql<qr && calc(q[qr-1], q[qr])>calc(q[qr], p[pos1])) --qr;
				q[++qr]=p[pos1];
				++pos1;
			}
			while (ql<qr && p[i]>q[ql+1] && calc(q[ql], q[ql+1])<2*p[i]) {
				// cout<<"a: "<<a[p[i]]<<' '<<a[q[ql+1]]<<endl;
				// cout<<"k: "<<q[ql]<<' '<<q[ql+1]<<' '<<calc(q[ql], q[ql+1])<<' '<<2*p[i]<<endl;
				++ql;
			}
			// cout<<"tran: "<<p[i]<<' '<<q[ql]<<endl;
			if (p[i]>q[ql]) {
				dp[p[i]]=max(dp[p[i]], dp[q[ql]]-sum(p[i]-q[ql]-1));
				// cout<<"tran: "<<p[i]<<' '<<q[ql]<<' '<<dp[q[ql]]-sum(p[i]-q[ql]-1)<<' '<<dp[q[ql]]<<endl;
			}
		}
		sort(p+l, p+r+1, cmp1);
		cdq(mid+1, r);
	}
	void solve() {
		memset(dp, 128, sizeof(dp));
		a[0]=-INF; a[n+1]=INF; dp[0]=INF;
		for (int i=0; i<=n; ++i) p[i]=i;
		sort(p, p+n+1, cmp1);
		cdq(0, n);
		// cout<<"dp: "; for (int i=0; i<=n; ++i) cout<<dp[i]<<' '; cout<<endl;
		for (int i=0; i<=n; ++i) dp[n+1]=max(dp[n+1], dp[i]-sum(n-i));
		printf("%lld\n", dp[n+1]);
		exit(0);
	}
}

signed main()
{
	freopen("skip.in", "r", stdin);
	freopen("skip.out", "w", stdout);

	n=read();
	for (int i=1; i<=n; ++i) a[i]=read();
	// force::solve();
	// task1::solve();
	task::solve();

	return 0;
}