最大公约数

题目描述 你有一个环，环上有�个正整数。你能将环切成�段，每段包含一个或者多个数字。

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

输入格式 第一行一个整数�，表示环上的数字个数。

接下来一行包含�个正整数，第�个数�� 表示环上第�个数。

输出格式 输出�行，第�行表示切成�段时的最大优美程度。

样例输入 1 7 2 3 3 3 3 3 3

样例输出 1 20 5 2 2 1 1 1

样例输入输出 2 见下发文件。

数据规模 共 10 个测试点。

测试点 1,2 满足� ≤ 20。

测试点 3,4,5 满足�� ≤ 5。

对于所有数据，满足 1 ≤ � ≤ 2000,1 ≤ �� ≤ 5 × 107 。