Team Partitioning with Lexicographical Optimization

Little X is forming a team. Initially, only Little X is present with an ability value \(v_0 = 10^{10^{100}}\). In the next \(n\) days, one new member is recruited per day; the ability of the member joining on day \(i\) is \(v_i\). To better manage the team, Little X wants to partition the team (indexed from 0 to \(k\) for a given number \(k\) of recruited members, with member 0 being himself) into contiguous groups.

Formally, suppose there are \(k\) recruited members (with indices \(1,2,\dots,k\)) and index 0 for Little X. Little X wants to find a sequence of indices

[ 0 = a_0 < a_1 < \dots < a_m = k+1 ]

such that for every \(0 \le i < m-1\) the following inequality holds:

[ \sum_{j=a_i}^{a_{i+1}-1} v_j > \sum_{j=a_{i+1}}^{a_{i+2}-1} v_j. ]

Furthermore, Little X wishes the sequence \( (a_m, a_{m-1}, \dots, a_1) \) to be lexicographically maximum. In other words, subject to \(a_m=k+1\) (which is fixed), he wants \(a_{m-1}\) as large as possible; subject to that, \(a_{m-2}\) as large as possible; and so on.

Your task is: for every \(k = 1,2,\dots,n\), determine the value of

[ \sum_{i=0}^{m} i \times a_i. ]

Note: Since \(v_0 = 10^{10^{100}}\) is astronomically large, the inequality for the very first group (which always contains index 0) is always satisfied regardless of the partition of the remaining indices. Hence, the optimal partition is determined by how you partition the recruits (indices 1 to \(k\)). In order to get a lexicographically maximum reverse sequence \((a_m, a_{m-1}, \dots, a_1)\), one should split the recruits into as many groups as possible by making each group as short as possible from the right while satisfying for every adjacent pair of groups (when processed from left to right) the sum condition.

A natural greedy strategy on the recruits (indices 1 through \(k\)) is as follows:

1. Consider the last recruit as a group by itself.
2. Iterate from right to left accumulating a running sum. Whenever the accumulated sum becomes strictly greater than the sum of the group immediately to its right, mark a new group boundary.

Assume the partition of the recruits obtained by this procedure is given by boundaries \(b_1, b_2, \dots, b_t\) (in increasing order) where the groups are \([b_1, b_2-1], [b_2, b_3-1], \dots, [b_t, k]\). Then the full partition of indices \(0,1,2,\dots,k,k+1\) is:

[ a_0 = 0,; a_1 = b_1,; a_2 = b_2,; \dots, ; a_{t} = b_{t},; a_{t+1} = k+1. ]

You are to output \(\sum_{i=0}^{m} (i \times a_i)\) (with \(m = t+1\)) for each \(k = 1, 2, \dots, n\), each on a separate line.

inputFormat

The first line contains an integer \(n\) (the number of days/recruits).
The second line contains \(n\) space‐separated integers \(v_1, v_2, \dots, v_n\) representing the ability values of the recruits.

outputFormat

Output \(n\) lines. The \(k\)-th line (for \(1 \le k \le n\)) should contain a single integer: the value of \(\sum_{i=0}^{m} (i \times a_i)\) for the team formed when there are \(k\) recruits (with indices from 1 to \(k\)).

sample

1
5

5

</p>