#include <stdio.h>

long long N, v[100005], arb[1000000], arb2[1000000], arb3[1000000], val, pos;
long long s, S;

long long min(long long x, long long y) { return x < y ? x : y;}

void build(long long nod, long long st, long long dr)
{
	long long m = (st + dr) / 2;
	if (st == dr)
	{
		arb[nod] = val;
		arb2[nod] = pos;
	}
	else
	{
	
		if (pos <= m) build(2 * nod, st, m);
		else build(2 * nod + 1, m + 1, dr);
	

		if (arb[2 * nod] + arb3[2 * nod] <= arb[2 * nod + 1] + arb3[2 * nod + 1] || !arb[2 * nod + 1])
		{
			arb[nod] = arb[2 * nod] + arb3[2 * nod];
			arb2[nod] = arb2[2 * nod];
		}
		else 
		{
			arb[nod] = arb[2 * nod + 1] + arb3[2 * nod + 1];
			arb2[nod] = arb2[2 * nod + 1];
		}	
	}
}

void update(long long nod, long long st, long long dr, long long l, long long r)
{
	long long m = (st + dr) / 2;

	if (l <= st && dr <= r)
	{
		arb3[nod] += val;		
	}
	else
	{
		if (r < dr && r >= st) 
		{
			update(2 * nod, st, m, l, r);
			update(2 * nod + 1, m + 1, dr, l, r);
		}
	}
}
	


int main()
{
	freopen("biscuiti.in","r",stdin);
	freopen("biscuiti.out","w",stdout);

	long long i;
	scanf("%lldd",&N);
	for (i = 1; i <= N; i++)
	{
		scanf("%lldd",&v[i]);
		s += v[i]; val = v[i]; pos = i;
		build(1,1,N);
	}

	for (i = 1; i <= N; i++)
	{
		S += arb[1] + arb3[1];
	//	arb3[1] = 0;
		pos = arb2[1];

		val = i;
		update(1,1,N,1,pos);
		val = (1<<30);
		build(1,1,N);
		
	}
	printf("%lld",S - s);
	return 0;
}