\problemname{Sequence}

\noindent
A sequence of positive integers $(x_1,\ldots,x_m)$ is \emph{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 \emph{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$.

\section*{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$.

\section*{Output}

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

\section*{Constraints and Scoring}

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

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.

\medskip
\begin{tabular}{lll}
Group & Points & Constraints \\\hline
$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$ \\ % constraint:uniformweights
$4$   & $9$ & $n\leq 1400$, $w_1=\cdots=w_n = 1$ \\
$5$   & $45$ & $n\leq 5000$\\
$6$   & $15$ & \emph{No additional constraints}
\end{tabular}
