Hide

Problem F
Ciąg liczb

Languages da de en et fi lt lv pl uk

Ciąg dodatnich liczb całkowitych $(x_1,\ldots ,x_ m)$ jest dobry jeśli $x_1 = 1$ oraz dla każdego $1 < j \leq m$ mamy albo $x_ j=x_{j-1}+1$ albo $x_ j=x_ k\cdot x_ l$ dla pewnych $k$ oraz $l$ spełniających $0< k\leq l< j$. Na przykład, oba ciągi $(1,1)$ oraz $(1,2)$ są dobre, ale ciąg $(1,3)$ nie jest dobry. Dla danych $n$ liczb całkowitych $w_1,\ldots ,w_ n$ definiujemy wagę ciągu liczb całkowitych $(x_1,\ldots ,x_ m)$ spełniającego $1\leq x_ j \leq n$ dla każdego $1\leq j\leq m$ jako

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

Na przykład, mając wagi $w_1=10, w_2=42,w_3= 1$, wagą ciągu $(1,1)$ jest $20$, a wagą ciągu $(1,3)$ jest $11$. Dla $1\leq v\leq n$ definiujemy $s_ v$ jako najmniejszą możliwą wagę dobrego ciągu zawierającego wartość $v$.

Twoim zadaniem jest wyznaczenie wartości $s_1,\ldots ,s_ n$.

Wejście

W pierwszym wierszu wejścia znajduje się liczba całkowita $n$, będąca liczbą wag. Kolejne $n$ wierszy zawierają liczby całkowite wag $w_1, \ldots , w_ n$.

Wyjście

Wypisz $n$ wierszy zawieraje kolejno: $s_1$, $\ldots $, $s_ n$.

Ograniczenia i punktacja

Zawsze jest spełnione $1\leq n \leq 30\, 000$ oraz $1\leq w_ i \leq 10^6$ dla każdego $1\leq i \leq n$.

Twoje rozwiązanie zostanie przetestowane na zestawie grup testowych, z których każda warta jest pewną liczbę punktów. Każda grupa testowa zawiera zestaw przypadków testowych. Aby uzyskać punkty za grupę testową musisz rozwiązać wszystkie przypadki testowe w tej grupie. Twój ostateczny wynik będzie maksymalnym wynikiem pojedynczego zgłoszenia.

Grupa

Punkty

Ograniczenia

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

Brak dodatkowych ograniczeń

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