题目描述
你有一个环,环上有$n$个正整数。你能将环切成$k$段,每段包含一个或者多个数字。
对于一个切分方案,优美程度为每段数字和的最大公约数,你想使切分方案的优美程度最大,对于$k=1,2,\dots, n$输出答案。
输入格式
第一行一个整数$n$,表示环上的数字个数。
接下来一行包含$n$个正整数,第$i$个数$a_i$表示环上第$i$个数。
输出格式
输出$n$行,第$i$行表示切成$i$段时的最大优美程度。
样例输入1
7
2 3 3 3 3 3 3
样例输出1
20
5
2
2
1
1
1
样例输入输出2
见下发文件。
数据规模
共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$。