Sequence

문제

A sequence of positive integers $(x_1,\dots ,x_m)(x\_1,\backslash ldots,x\_m)$ is good if $x_1=1x\_1\; =\; 1$ and for each we have either $x_j=x_{j-1}+1x\_j=x\_\{j-1\}+1$ or $x_j=x_k\cdot x_{l}x\_j=x\_k\backslash cdot\; x\_l$ for some $kk$ and $ll$ with . For instance, the sequences $(1,1)(1,1)$ and $(1,2)(1,2)$ are both good, but the sequence $(1,3)(1,3)$ is not good. For $nn$ given integers $w_1,\dots ,w_{n}w\_1,\backslash ldots,w\_n$ define the weight of an integer sequence $(x_1,\dots ,x_m)(x\_1,\backslash ldots,x\_m)$ satisfying $1\le x_j\le n1\backslash leq\; x\_j\; \backslash leq\; n$ for each $1\le j\le m1\backslash leq\; j\backslash leq\; m$ as \[ w_{x_1} +\cdots +w_{x_m}\,.\] For instance, given the weights $w_1=10,w_2=42,w_3=1w\_1=10,\; w\_2=42,w\_3=\; 1$, the weight of the sequence $(1,1)(1,1)$ is $2020$ and the weight of the sequence $(1,3)(1,3)$ is $1111$. For $1\le v\le n1\backslash leq\; v\backslash leq\; n$, define $s_{v}s\_v$ as the smallest possible weight of a good sequence containing the value $vv$.

Your task is to determine the values $s_1,\dots ,s_{n}s\_1,\backslash ldots\; ,s\_n$.

입력

The first line of input consists of the integer $nn$, the number of weights. The next $nn$ lines contain the integer weights $w_1,\dots ,w_{n}w\_1,\; \backslash ldots,\; w\_n$.

출력

Print $nn$ lines containing $s_{1}s\_1$, $\dots \backslash ldots$, $s_{n}s\_n$ in order.