sequence — BOI contest
Task type: batch | Time limit: 1 s | Memory limit: 1024 MB | Difficulty: 24
Algorithms: shortest path, number theory, dynamic programming

## Sequence
**Problem ID:** sequence

A sequence of positive integers $(x_1, ..., x_m)$ is *good* if $x_1 = 1$ and for each $1 < j \le m$ we have either $x_j = x_{j-1} + 1$ or $x_j = x_k \cdot x_l$ for some $k$ and $l$ with $0 < k \le l < j$. For instance, the sequences $(1, 1)$ and $(1, 2)$ are both good, but the sequence $(1, 3)$ is not good. For $n$ given integers $w_1, ..., w_n$, define the *weight* of an integer sequence $(x_1, ..., x_m)$ satisfying $1 \le x_j \le n$ for each $1 \le j \le m$ as:

$w_{x_1} + ... + w_{x_m}$.

For instance, given the weights $w_1 = 10, w_2 = 42, w_3 = 1$, the weight of the sequence $(1, 1)$ is 20 and the weight of the sequence $(1, 3)$ is 11. For $1 \le v \le n$, define $s_v$ as the smallest possible weight of a good sequence containing the value $v$.

Your task is to determine the values $s_1, ..., s_n$.

## Input

The first line of input consists of the integer $n$, the number of weights. The next $n$ lines contain the integer weights $w_1, ..., w_n$.

## Output

Print $n$ lines containing $s_1, ..., s_n$ in order.

## Constraints and Scoring

We always have $1 \le n \le 30\,000$ and $1 \le w_i \le 10^6$ for each $1 \le i \le n$.

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.

| Group | Points | Constraints              |
|-------|--------|--------------------------|
| 1     | 11     | $n \le 10$               |
| 2     | 10     | $n \le 300, w_1 = ... = w_n = 1$ |
| 3     | 10     | $n \le 300, w_1 = ... = w_n$   |
| 4     | 9      | $n \le 1400, w_1 = ... = w_n - 1$ |
| 5     | 45     | $n \le 5000$              |
| 6     | 15     | No additional constraints |

| Sample Input 1 | Sample Output 1 |
|----------------|-----------------|
| 3              | 10              |
| 10             | 52              |
| 42             | 53              |
| 1              |                 |

Starter code: