Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
Statistics

题目描述

给你一个数列 $A_{1..n}(A_i>0)$,对于 $1..n$ 中的每个 $K$,你要把它分成 $K$ 个非空的连续段。

对每段分别求和,得到 $K$ 个数,请你最大化它们的最大公约数,并输出这个值。

输入格式

第一行一个数 $n$

第二行 $n$ 个数 $A_{1..n}$

输出格式

一行 $n$ 个数,第 $i$ 个数表示 $K=i$ 时的答案

样例

样例输入 1

12
1 1 4 5 1 4 1 9 1 9 8 10

样例输出 1

54 27 9 6 3 2 2 2 1 1 1 1

样例 2

见下发文件

数据范围

子任务编号 分数 $n\leqslant$ $\sum A_i\leqslant$
$1$ $20$ $10^4$ $10^4$
$2$ $80$ $10^6$ $2\times 10^7$