题目描述

给定一个长度为 $n$ 的序列 $w_1,w_2,\cdots,w_n$。称一个序列 $x_1,\cdots,x_m$ 是好的，当且仅当每个 $x_i$ 都是 $[1,n]$ 中的正整数，且 $x_1=1$，且对于 $i=2,\cdots,m$ 都有 $x_i=x_{i-1}+1$ 或存在正整数 $1\le j,k<i$ 满足 $x_i=x_jx_k$。一个好序列的权值定义为 $\sum\limits_{i=1}^mw_{x_i}$。

例如，若 $n=3$ 而 $w_1=10,w_2=42,w_3=1$，则 $[1,1]$ 为权值为 $20$ 的好序列，$[1,2]$ 为权值为 $52$ 的好序列，$[1,3]$ 不是好序列。

对于每个 $v=1,2,\cdots,n$，试求出所有包含 $v$ 的好序列的最小可能权值。

输入格式

第一行一个正整数 $n$。

接下来 $n$ 行，第 $i$ 行一个正整数 $w_i$。

输出格式

输出 $n$ 行，第 $i$ 行一个正整数表示 $v=i$ 时的答案。

3
10
42
1

10
52
53

提示

【数据范围】

对于 $100\%$ 的数据，$1\le n\le 30\,000$，$1\le w_i\le 10^6$。