最大公约数

题目描述

你有一个环，环上有 $n$ 个正整数。你能将环切成 $k$ 段，每段包含一个或者多个数字。

对于一个切分方案，优美程度为每段数字和的最大公约数，你想使切分方案的优美程度最大，对于 $k=1,2,\dots, n$ 输出答案。

输入格式

第一行一个整数 $n$，表示环上的数字个数。

接下来一行包含 $n$ 个正整数，第 $i$ 个数 $a_i$ 表示环上第 $i$ 个数。

输出格式

输出 $n$ 行，第 $i$ 行表示切成 $i$ 段时的最大优美程度。

样例输入

7
2 3 3 3 3 3 3

样例输出

20
5
2
2
1
1
1

数据范围

共 10 个测试点。

测试点 $1, 2$ 满足 $n\leq 20$。

测试点 $3, 4, 5$ 满足$a_i\leq 5$。

对于所有数据，满足 $1\leq n\leq 2000, 1\leq a_i\leq 5\times 10^7$。

提示

见下发文件。