Problem C
Sequence
Languages
da
de
en
et
fi
lt
lv
pl
uk
Послідовність $(x_1,\ldots ,x_ m)$ невід’ємних цілих чисел називається хорошою, якщо $x_1 = 1$, а для кожного $1 < j \leq m$ виконується або $x_ j=x_{j-1}+1$, або $x_ j=x_ k\cdot x_ l$ для деяких $k$ та $l$ з $0< k\leq l< j$. Наприклад, послідовності $(1,1)$ та $(1,2)$ є хорошими, а послідовність $(1,3)$ не є хорошою. Для заданих $n$ цілих чисел $w_1,\ldots ,w_ n$ визначимо вагу цілої послідовності $(x_1,\ldots ,x_ m)$, що задовольняє $1\leq x_ j \leq n$ для кожного $1\leq j\leq m$, як
\[ w_{x_1} +\cdots +w_{x_ m}\, . \]Наприклад, при $w_1=10$, $w_2=42$ та $w_3=1$, вага послідовності $(1,1)$ дорівнює $20$, а вага послідовності $(1,3)$ дорівнює $11$. Для $1\leq v\leq n$ визначимо $s_ v$ як найменшу можливу вагу хорошої послідовності, що містить значення $v$.
Ваше завдання полягає у визначенні значень $s_1,\ldots ,s_ n$.
Вхідні дані
Перший рядок містить ціле число $n$ — кількість ваг. Наступні $n$ рядків містять цілі числа $w_1, \ldots , w_ n$.
Вихідні дані
Виведіть $n$ рядків, що містять $s_1$, $\ldots $, $s_ n$ відповідно.
Обмеження та оцінювання
Ми завжди маємо: $1\leq n \leq 30\, 000$ та $1\leq w_ i \leq 10^6$ для кожного $1\leq i \leq n$.
Ваше рішення буде перевірено на наборі тестових груп, кожна з яких має певну кількість балів. Кожна група містить набір тестових випадків. Щоб отримати бали за групу тестів, потрібно пройти всі тестові випадки в цій групі. Ваш кінцевий бал буде максимальною кількістю балів за одне відправлення.
|
Група |
Бали |
Обмеження |
|
$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$ |
Немає додаткових обмежень |
| Sample Input 1 | Sample Output 1 |
|---|---|
3 10 42 1 |
10 52 53 |
