Waging War Peacefully

The Polymath civilization is known to have fought a large-scale war called the First Donga War around 8500 BC to subjugate its neighbor Scienceboard. You are studying the army tactics of the Polymath civilization at that time. Fortunately, you obtained some useful information from old documents.

According to their book of tactics, the army of the Polymath civilization was formed into a precise rectangular formation. That is, a rectangle with $X$ rows and $Y$ columns is filled by exactly $XY$ soldiers. Cases where the number of soldiers did not divide exactly, leaving some soldiers left over or short, were not allowed.

Since the Polymath civilization had originally subjugated many small neighboring countries with its strong military power, its army also contained $N$ different ethnic groups. In particular, records show that among the soldiers who took part in the First Donga War, exactly $A_i$ soldiers were from the $i$-th ethnic group.

The Polymath civilization discriminated against its citizens based on ethnic origin, and the army was affected by this as well. In particular, when $i<j$, a soldier from the $i$-th ethnic group always had to 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 had a slight problem: whenever soldiers from different ethnic groups were adjacent side by side, a fight always broke 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$.

The army officers of the Polymath civilization used peace stones to prevent fights. Using the power of a peace stone prevents 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, then the number of pairs of adjacent soldiers from different ethnic groups must be at most $k$ for no fight to occur.

Through various records, you discovered that the officers of the Polymath civilization believed that the wider the formation was, that is, the larger $Y$ was, the stronger the army was. Therefore, you conjecture that the formation used in the First Donga War was also a perfectly rectangular formation with the largest $Y$ value among formations where no fight occurs. However, since you have not yet determined exactly how many peace stones the Polymath civilization had, you decided 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, output the maximum possible value of $Y$ for each $k$ with $0 \le k \le N-1$, separated by spaces.

• $1 \le N \le 10^6$
• $1 \le A_i \le 10^{18}$
• $M \le 10^{18}$ (where $M = \sum_{i=1}^N A_i$)