http://www.51nod.com/Challenge/Problem.html#problemId=1023
#include<bits/stdc++.h> using namespace std; const int maxn = 5e4+1; long long a[maxn], b[maxn], tot, ans; void combine(int x) { long long i, d, temp; temp = b[x] + b[x+1]; for(i = x+1; i <= tot-1; i++) { b[i] = b[i+1]; } ans += temp, tot -= 1; for(i = x-1; i >= 1 && b[i] <= temp; i--) { b[i+1] = b[i]; } b[i+1] = temp; while(i >= 2 && b[i-1] <= b[i+1]) { d = tot-i; combine(i-1); i = tot-d; } } int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i ++) { scanf("%lld", &a[i]); b[i] = a[i]; } a[++n] = LLONG_MAX; for(int i = 1; i <= n; i ++) { b[++tot] = a[i]; while(tot >= 3 && b[tot-2] <= b[tot]) combine(tot-2); } printf("%lld\n", ans); return 0; }