#include<cstdio>
#include<set>
long long a[1111111];
long long s[1111111];
long long ss[1111111];
long long d[1111111];
std::set<std::pair<long long,long long> > S;
std::set<std::pair<long long,long long> >::iterator it1,it2;
std::pair<long long,long long> P;
int main()
{
double tx,ty;
int i,j,n;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
S.insert(std::make_pair(0,0));
for(i=n;i>=0;i--)
{
s[i]=s[i+1]+a[i];
ss[i]=ss[i+1]+s[i+1];
while(S.size()>=2)
{
it1=S.end();
it1--;
it2=it1;
it2--;
if(i*it1->first+it1->second>i*it2->first+it2->second)break;
S.erase(it1);
}
it1=S.end();
it1--;
d[i]=i*it1->first+it1->second+ss[i];
P=std::make_pair(s[i],d[i]-ss[i]-i*s[i]);
it1=it2=S.lower_bound(std::make_pair(P.first,-9e18));
if(it1!=S.end())
{
if(it1->first==P.first&&it1->second>=P.second)continue;
if(it1!=S.begin())
{
it2--;
tx=-1.*(it1->second-it2->second)/(it1->first-it2->first);
ty=it1->first*tx+it1->second;
if(ty>=P.first*tx+P.second)continue;
}
}
while(1)
{
it1=it2=S.lower_bound(std::make_pair(P.first,-9e18));
if(it1==S.end())break;
if(it1->first==P.first&&it1->second<=P.second)
{
S.erase(it1);
continue;
}
it2++;
if(it2==S.end())break;
tx=-1.*(it1->second-it2->second)/(it1->first-it2->first);
ty=it1->first*tx+it1->second;
if(ty<=P.first*tx+P.second)S.erase(it1);
else break;
}
while(1)
{
it1=it2=S.lower_bound(std::make_pair(P.first,-1e18));
if(it1==S.begin())break;
it1--;
if(it1==S.begin())break;
it2=it1;
it2--;
tx=-1.*(it1->second-it2->second)/(it1->first-it2->first);
ty=it1->first*tx+it1->second;
if(ty<=P.first*tx+P.second)S.erase(it1);
else break;
}
S.insert(std::make_pair(P.first,P.second));
}
printf("%lld\n",d[0]);
}
