（以下内容绝大部分参考集训队作业和这篇博客，建议阅读原文获得更好的体验）
本题可以考虑这样一个贪心策略：每次选取对答案贡献最大的点加入，直到最大贡献为负。
事实上这个策略是正确的，下面来证明。（下设第 (i) 个数当前的贡献为 (w(i))，选取集合 (S) 的答案为 (val(S)) ）。
首先证明一个引理：
在上述策略下，如果 (ilt j,~ a_igt a_j)，那么 (i) 一定比 (j) 先选择（即 (w(i)gt w(j))）。
证明：因为加入先后的差异仅在于中间已选元素对两端的贡献：中间 (k) 对 (j) 的贡献为 (a_j)，对 (i) 的贡献为 (a_k)，我们只需证 (forall a_k,a_kge a_j)。故我们考虑对 ([i,j]) 中间的元素数量进行归纳证明：
- 假设 ([i,j]) 中有 (0) 个已选的元素，则显然先选择 (i)。
- 假设 ([i,j]) 中有 (x) 个已选的元素，因为 ([i,k]) 内选择元素数量显然严格小于 (x) ，所以 ([i,k]) 满足引理，故 (a_kge a_ige a_j) ，引理得证。
有了这个引理之后，我们考虑反证这个策略：假设 (val(Acup{x}cup C)lt val(Acup B)) （(x otin B,B eq empty)，(x) 为在策略下集合 (A) 下一个选择的元素，(C) 为任意集合）：
- 假设 (B) 中存在元素在 (x) 左边，设 (y) 为 (B) 中在 (x) 左边最靠右的元素，由策略可得 (w(x)ge w(y)) 。在 (x) 左边的元素对 (x,y) 的贡献为 (a_x,a_y) ，根据引理有 (a_yle a_x)；在 (y) 右边的元素贡献相同，(x,y) 中间没有元素。故选择 (x) 不会比选择 (y) 劣。
- 假设 (B) 中所有元素在 (x) 右边，考虑最左边的元素 (y) ，其他元素对 (x,y) 贡献相同，故选择 (x) 不会比选择 (y) 劣。
综上，假设不成立，所以原策略是正确的。
之后，我们可以动态维护所有的 (w(i))，需要支持区间加一个数，区间加 (a_i)，查询全局最大值。直接套用模板简单的数列题。复杂度可以做到根号。（没有代码 /kk）
通过这个结论可以得到一个重要推论：
设 (S_i) 为选择集合大小为 (i) 的一个最优解集合，则存在 (S_isub S_{i+1})。
这个推论可以帮助我们得到一个更优复杂度的做法。
我们考虑一个 (n^2) 的 DP：设 (f_{i,j}) 表示前 (i) 个元素，选了 (j) 个元素的答案：
由上面的推论可以得到：选择 (a_i) 的 (j) 一定是一段后缀。
（事实上这个结论有一个牛逼的证明方法，可以看这篇博客。）
所以上面的 DP 是一个分段函数，我们可以用平衡树维护差分数组，每次平衡树上二分找到分界点插入，然后后缀加即可。
复杂度 (O(nlog n))。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int gi()
{
char c=getchar(); int x=0,f=1;
for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0';
return x*f;
}
const int N=1e5+5;
int ch[N][2],sze[N],fa[N],n,rt,cnt;
ll val[N],tag[N],sum,ans;
void pushup(int x)
{
sze[x]=sze[ch[x][0]]+sze[ch[x][1]]+1;
}
void pushdown(int x)
{
if(!tag[x]||!x) return ;
tag[ch[x][0]]+=tag[x],tag[ch[x][1]]+=tag[x];
val[ch[x][0]]+=tag[x],val[ch[x][1]]+=tag[x];
tag[x]=0;
}
void rotate(int x)
{
int y=fa[x],z=fa[y];
int k=ch[y][1]==x,w=ch[x][!k];
ch[z][ch[z][1]==y]=x,ch[x][!k]=y,ch[y][k]=w;
fa[w]=y,fa[y]=x,fa[x]=z;
pushup(y);
}
void maintain(int x)
{
if(fa[x]) maintain(fa[x]);
pushdown(x);
}
void splay(int x, int k)
{
maintain(x);
while(fa[x]!=k)
{
int y=fa[x],z=fa[y];
if(z!=k) (ch[z][1]==y)^(ch[y][1]==x)?rotate(x):rotate(y);
rotate(x);
}
pushup(x);
if(!k) rt=x;
}
void insert(int& u, int f, int w, int rk)
{
if(!u)
{
u=++cnt;
sze[u]=1,fa[u]=f;
val[u]=1ll*w*(rk+1);
splay(u,0);
return ;
}
pushdown(u);
int now=rk+sze[ch[u][0]]+1;
if(val[u]<1ll*w*now) insert(ch[u][0],u,w,rk);
else insert(ch[u][1],u,w,now);
}
void dfs(int u)
{
if(!u) return ;
pushdown(u);
dfs(ch[u][0]);
sum+=val[u],ans=max(ans,sum);
dfs(ch[u][1]);
}
int main()
{
n=gi();
for(int i=1;i<=n;++i)
{
int w=gi();
insert(rt,0,w,0);
val[ch[rt][1]]+=w,tag[ch[rt][1]]+=w;
}
dfs(rt),printf("%lld
",ans);
}