Hide

Problem F
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