Minimum Weight Good Sequences

Given an integer (n) and a sequence of weights (w_1, w_2, \ldots, w_n), consider sequences (x_1, x_2, \ldots, x_m) satisfying the following conditions:

1. Every (x_i) is a positive integer between 1 and (n) (inclusive).
2. (x_1 = 1).
3. For every (i) with (2 \le i \le m), at least one of the following holds:
   • (x_i = x_{i-1} + 1), or
   • There exist indices (j, k) with (1 \le j, k < i) such that (x_i = x_j \times x_k).

A sequence satisfying the conditions above is called a good sequence. Its weight is defined as [ \sum_{i=1}^{m} w_{x_i}. ]

For each (v = 1, 2, \ldots, n), determine the minimum possible weight over all good sequences that contain the number (v) at least once. It is guaranteed that the sequence

[ [1, 2, \ldots, v] ]

is a valid good sequence (since for each (i \ge 2) we have (x_i = x_{i-1} + 1)). Thus, one valid upper bound for the answer for (v) is the prefix sum (w_1 + w_2 + \cdots + w_{v}); however, in some cases a sequence using the multiplication rule might yield a lower total weight. If no good sequence containing (v) exists, output -1 for that (v).

Example:
Let (n = 3) with (w_1 = 10), (w_2 = 42), and (w_3 = 1). Then:

• The sequence [1, 1] is good since for the second element we have \(1 = 1 \times 1\), and its weight is \(10 + 10 = 20\).
• The sequence [1, 2] is good because \(2 = 1 + 1\), with weight \(10 + 42 = 52\).
• The sequence [1,2,3] is also good (since \(3 = 2 + 1\)) with weight \(10 + 42 + 1 = 53\). Note that the sequence [1,3] is not good since neither \(3 = 1+1\) nor can it be obtained as a product from two earlier elements.

Thus, one acceptable set of answers for this example would be:

• For \(v = 1\): 20 (using the sequence [1, 1])
• For \(v = 2\): 52 (using the sequence [1, 2])
• For \(v = 3\): 53 (using the sequence [1, 2, 3])

Your task is to compute, for each (v), the minimum possible weight of any good sequence that contains (v).

inputFormat

The first line contains an integer \(n\) representing the length of the weight sequence. The second line contains \(n\) space-separated integers \(w_1, w_2, \ldots, w_n\), where \(w_i\) denotes the weight associated with number \(i\).

outputFormat

Output \(n\) integers separated by spaces in one line. The \(v\)-th integer should be the minimum possible weight of any good sequence that contains \(v\). If no such sequence exists for a particular \(v\), output -1 instead.

sample

3
10 42 1

20 52 53

</p>