这是一个神奇的算法,叫GarsiaWachs算法,不会。
小数据可以用四边形不等式优化。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define gc getchar()
using namespace std;
const int N=50005;
inline void qr(int &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int a[N];
int n,m,ans;
void merge(int k)
{
    int tmp=a[k]+a[k-1];
    ans+=tmp;
    for(int i=k;i<m;i++)
        a[i]=a[i+1];
    --m;int j=1;
    for(j=k-1;j>1&&a[j-1]<tmp;j--)
        a[j]=a[j-1];
    a[j]=tmp;
    while(j>=3&&a[j]>=a[j-2])
    {
        int d=m-j;
        merge(j-1);
        j=m-d;
    }
}
int main()
{
    while(qr(n),n)
    {
        for(int i=1;i<=n;i++)qr(a[i]);
        m=1;ans=0;
        for(int i=2;i<=n;i++)
        {
            a[++m]=a[i];
            while(m>=3&&a[m-2]<=a[m])
                merge(m-1);
        }
        while(m>1)merge(m);
        qw(ans);puts("");
    }
    return 0;
}