$4191$. 「BalticOI $2023$」Sequence

传统 $1000$ ms $1024$ MiB
$12$ 通过
$38$ 提交

题目描述

题目译自 BalticOI $2023$ Day2「Sequence」

一列整数 $(x_1,\ldots,x_m)$ 是好的，如果 $x_1=1$ 并且对于每个 $1<j\le m$，要么有 $x_j=x_{j-1}+1$，要么对于某个 $k$ 和 $l$ 满足 $0<k\le l<j$ 有 $x_j=x_k\cdot x_l$。

例如，序列 $(1,1)$ 和 $(1,2)$ 都是好的，但是序列 $(1,3)$ 不是好的。

对于给定的 $n$ 个整数 $w_1,\ldots,w_n$，定义一个对于 $1\le j\le m$ 都满足 $1\le x_j\le n$ 的整数序列 $(x_1,\ldots,x_m)$ 的权重为

例如，给定的权重 $w_1=10$, $w_2=42$, $w_3=1$：

• 序列 $(1,1)$ 的权重为 $20$
• 序列 $(1,3)$ 的权重为 $11$

对于 $1\le v\le n$，定义 $s_v$ 为包含 $v$ 的好序列可能的最小权重。

你的任务是确定 $s_1,\ldots,s_n$。

输入格式

第一行一个整数 $n$，表示权重序列的长度。

接下来 $n$ 行，每行一个整数 $w_i$，表示权重序列。

输出格式

输出 $n$ 行，第 $i$ 行输出 $s_i$。

样例

输入

3
10
42
1

输出

10
52
53

数据范围与提示

对于全部数据，满足：

• $1\le n\le 3\cdot 10^4$
• $1\le w_i\le 10^6$（对于 $1\le i\le n$）

详细子任务附加限制及分值如下表。