Hide

Problem C
Seka

Languages da de en et fi lt lv pl uk

Natūraliųjų skaičių seka $(x_1,\ldots ,x_ m)$ vadinama gera, jeigu $x_1 = 1$ ir kiekvienam $1 < j \leq m$ galioja arba $x_ j=x_{j-1}+1$, arba $x_ j=x_ k\cdot x_ l$, kur $k$ ir $l$ yra tokie skaičiai, kuriems galioja $0< k\leq l< j$.

Pavyzdžiui, abidvi sekos $(1,1)$ ir $(1,2)$ yra geros, bet seka $(1,3)$ – ne.

Duotiesiems $n$ skaičių $w_1,\ldots ,w_ n$, sekos $(x_1,\ldots ,x_ m)$, kur kiekvienam $1\leq j\leq m$ galioja $1\leq x_ j \leq n$ , svoris apibrėžiamas taip:

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

Pavyzdžiui, duoti svoriai $w_1=10, w_2=42,w_3= 1$. Tuomet sekos $(1,1)$ svoris yra $20$, o sekos $(1,3)$$11$.

Kiekvienam $1\leq i\leq n$ pažymėkime mažiausią geros sekos, kurioje yra $i$, svorį $s_ i$.

Raskite $s_1,\ldots ,s_ n$ reikšmes.

Pradiniai duomenys

Pirmoje įvesties eilutėje pateiktas svorių skaičius $n$ (sveikasis skaičius). Kitose $n$ eilučių pateikti svoriai – sveikieji skaičiai $w_1, \ldots , w_ n$.

Rezultatai

Išveskite $n$ eilučių. Jose iš eilės pateikite $s_1$, $\ldots $, $s_ n$.

Ribojimai ir vertinimas

Visada galioja $1\leq n \leq 30\, 000$ ir $1\leq w_ i \leq 10^6$ kiekvienam $1\leq i \leq n$.

Jūsų sprendimas bus testuojamas su keliomis testų grupėmis, kurių kiekviena verta tam tikro skaičiaus taškų. Kiekviena testų grupė sudaryta iš įvairių testų. Testų grupės taškai skiriami tik išsprendus visus grupės testus. Galutinis taškų skaičius lygus daugiausiai surinkusio sprendimo taškų skaičiui.

Grupė

Taškai

Papildomi ribojimai

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

nėra

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