不妨考虑一个 DP。设 $f _ {i, j}$ 表示依次考虑 $[i, n]$ 中的物品，带上了 $j$ 个，最小代价。由于是正扫，能加就加，因此倒着 DP。

观察大样例不难发现 $f _ i$ 是单调的，带的物品越多，最小代价越大。

考虑转移。

钦定 $f _ {i, 0} = 0$，这是有道理的。

设 $k$ 满足 $f _ {i + 1, k} < w _ i$，并且最大。

• 对于 $j \le k$，$f _ {i, j}$ 可以直接继承 $f _ {i + 1, j}$ 的值（也就是不选取 $i$），并且这是最优的，因为如果选取 $i$ 的话代价一定大于 $w _ i$。

• 对于 $j > k$，是不可以不选取 $i$ 直接继承的，因为 $f _ {i + 1, j} \ge w _ i$，从前往后扫到 $i$，能拿就直接拿了，所以 $f _ {i, j} \gets f _ {i + 1, j - 1} + w _ i$。

直接做是 $O(n ^ 2)$ 的。

第一部分转移就是保持不变；第二部分，形如先对 $[k + 1, n - i]$ 区间加 $w _ i$，然后在第 $k + 1$ 个数前插入 $f _ k + w _ i$。

容易数据结构优化，用平衡树维护区间加和单点插入即可，$k$ 这个位置可以在平衡树上二分找到（或者 FHQ-treap 这种树，直接按权值分裂）。

时间复杂度 $O(n \log n)$。

#include <bits/stdc++.h>
#define F(i, a, b) for(int i = (a); i <= (b); ++i)
#define dF(i, a, b) for(int i = (a); i >= (b); --i)

using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int, LL> pii;
const int N = 5e5 + 5;

int n, w[N];

int rt, ls[N], rs[N], rnd[N]; LL val[N], tag[N];
static mt19937 Rand;
uniform_int_distribution<int> rng(1, 1e9);
void Maketag(int u, LL k) { val[u] += k, tag[u] += k; }
void Pushdown(int u) {
  if (ls[u]) Maketag(ls[u], tag[u]);
  if (rs[u]) Maketag(rs[u], tag[u]);
  tag[u] = 0;
}
int Merge(int u, int v) {
  if (!u || !v) return u | v;
  Pushdown(u), Pushdown(v);
	if (rnd[u] >= rnd[v]) return rs[u] = Merge(rs[u], v), u;
	else return ls[v] = Merge(u, ls[v]), v;
}
void Split(LL k, int &x, int &y, int u) {
	if (!u) return x = y = 0, void();
  Pushdown(u);
	if (val[u] <= k) Split(k, rs[x = u], y, rs[u]);
	else Split(k, x, ls[y = u], ls[u]);
}
int Query(int u) {
  if (!u) return 0;
  while (rs[u]) Pushdown(u), u = rs[u];
  return val[u];
}
void Newnode(int u, int k) { val[u] = k, tag[u] = 0, rnd[u] = rng(Rand); }
void Solve(int u) {
  Pushdown(u);
  if (ls[u]) Solve(ls[u]);
  cout << val[u] << " ";
  if (rs[u]) Solve(rs[u]);
}

int main() {
  // freopen("zyq.in", "r", stdin);
  // freopen("zyq.out", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  F(i, 1, n) cin >> w[i];
  Newnode(rt = n, w[n]);
  dF(i, n - 1, 1) {
    int u = 0, v = 0; Split(w[i] - 1, u, v, rt);
    Newnode(i, Query(u) + w[i]), Maketag(v, w[i]);
    rt = Merge(Merge(u, i), v);
  }
  Solve(rt);
  return 0;
}