31979번 - Sequence 서브태스크다국어

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$.

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$.

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

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