Preparing for War

The kingdom of Polymath is preparing for war to conquer its neighbor Scienceboard. You have been asked to design the battle formation for the war, and you are now studying formations.

Given the terrain of the war zone, the most efficient formation appears to be a rectangular one. That is, a rectangle with $X$ rows and $Y$ columns filled by exactly $XY$ soldiers. If the number of soldiers does not divide evenly and some are left over or missing, such a formation cannot be made.

Since the Polymath civilization has long subjugated many small neighboring countries with its strong military, its army contains soldiers from $N$ different ethnic groups. In particular, the number of soldiers from the $i$-th ethnic group participating in this war is exactly $A_i$.

Because rank depends on ethnic group, the positions of the soldiers cannot be assigned arbitrarily. In particular, when $i<j$, a soldier from the $i$-th ethnic group must always stand in front of a soldier from the $j$-th ethnic group. Here, a soldier at row $a$, column $b$ standing in front of a soldier at row $a'$, column $b'$ means that one of the following two conditions holds.

• $a<a'$
• $a=a'$ and $b<b'$

However, this arrangement has a slight problem: if soldiers from different ethnic groups are adjacent side by side, a fight will break out. Here, a soldier at row $a$, column $b$ and a soldier at row $a'$, column $b'$ being adjacent side by side means that $a=a'$ and $|b-b'|=1$.

When you report this problem, the army officers of the kingdom decide to use peace stones to prevent fights. Using the power of a peace stone can prevent a fight even when soldiers from different ethnic groups are adjacent, but one stone can prevent only one fight. That is, if you have $k$ peace stones, fights will not break out only when the number of adjacent pairs of soldiers from different ethnic groups is at most $k$.

The army officers believe that the wider the formation is, that is, the larger $Y$ is, the stronger the army is. Therefore, you must find a formation satisfying the above conditions with the largest possible value of $Y$. However, information about the peace stones is a state secret, so you do not know exactly how many peace stones there are. Thus, you decide to find the maximum possible value of $Y$ for every integer $k$ with $0 \le k \le N-1$.

The first line gives the number of ethnic groups $N$.

The next line gives the number of soldiers in each ethnic group, $A_1, A_2, \cdots, A_N$.

On the first line, print the maximum possible value of $Y$ for every integer $k$ with $0 \le k \le N-1$, separated by spaces.

• $1 \le N \le 10^3$
• $1 \le A_i \le 10^6$
• $M \le 10^6$ (where $M=A_1+A_2+\cdots+A_N$)