Hide

Problem F
Jada

Languages da de en et fi lt lv pl uk

Nimetame positiivsetest täisarvudest koosnevat jada $(x_1,\ldots ,x_ m)$ heaks, kui $x_1 = 1$ ja iga $1 < j \leq m$ korral kehtib kas $x_ j=x_{j-1}+1$ või $x_ j=x_ k\cdot x_ l$ mingite $k$ ja $l$ kohta, kus $0< k\leq l< j$. Näiteks on jadad $(1,1)$ ja $(1,2)$ mõlemad head, aga jada $(1,3)$ ei ole hea. On antud $n$ täisarvu $w_1,\ldots ,w_ n$. Nimetame arvujada $(x_1,\ldots ,x_ m)$ kaaluks, kus $1\leq x_ j \leq n$ iga $1\leq j\leq m$ kohta, arvu

\[ w_{x_1} +\cdots +w_{x_ m}\, . \]

Näiteks kui on antud $w_1=10, w_2=42,w_3= 1$, siis jada $(1,1)$ kaal on $20$ ja jada $(1,3)$ kaal on $11$. Tähistagu iga $1\leq v\leq n$ korral $s_ v$ vähimat võimalikku sellise hea jada kaalu, mis sisaldab väärtust $v$.

Sinu ülesanne on leida väärtused $s_1,\ldots ,s_ n$.

Sisend

Sisendi esimesel real on täisarv $n$ — kaalude arv. Järgmisel $n$ real on antud kaalud $w_1, \ldots , w_ n$.

Väljund

Trüki $n$ rida, milledel on vastavalt arvud $s_1$, $\ldots $, $s_ n$.

Piirangud ja hindamine

Alati kehtivad $1\leq n \leq 30\, 000$ ja $1\leq w_ i \leq 10^6$ iga $1\leq i \leq n$ kohta.

Selles ülesandes on testid jagatud gruppidesse, iga grupp on väärt mingi arvu punkte. Iga grupi eest saavad punkte vaid need lahendused, mis läbivad kõik sellesse gruppi kuuluvad testid. Sinu lõplik skoor on esituste maksimum.

Grupp

Punktid

Lisapiirangud

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

Lisapiirangud puuduvad.

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