Hide

Problem F
Sequence

Languages da de en et fi lt lv pl uk

A sequence of positive integers $(x_1,\ldots ,x_ m)$ is good if $x_1 = 1$ and for each $1 < j \leq 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\leq 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,\ldots ,w_ n$ define the weight of an integer sequence $(x_1,\ldots ,x_ m)$ satisfying $1\leq x_ j \leq n$ for each $1\leq j\leq m$ as

\[ w_{x_1} +\cdots +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\leq v\leq 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,\ldots ,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, \ldots , w_ n$.

Output

Print $n$ lines containing $s_1$, $\ldots $, $s_ n$ in order.

Constraints and Scoring

We always have $1\leq n \leq 30\, 000$ and $1\leq w_ i \leq 10^6$ for each $1\leq i \leq 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\leq 10$

$2$

$10$

$n\leq 300$, $w_1=\cdots =w_ n = 1$

$3$

$10$

$n\leq 300$, $w_1=\cdots =w_ n$

$4$

$9$

$n\leq 1400$, $w_1=\cdots =w_ n = 1$

$5$

$45$

$n\leq 5000$

$6$

$15$

No additional constraints

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