평화롭게 전쟁하기

폴리매스 문명은 기원전 8500년 경, 이웃 나라 사이언스보드를 복속시키기 위해 1차 동아전쟁이라 불리는 대규모 전쟁을 벌였던 것으로 알려져 있습니다. 당신은 그 당시 폴리매스 문명의 육군 전술에 관해 연구하고자 합니다. 다행히도, 당신은 고문헌에서 몇 가지 유용한 정보를 얻을 수 있었습니다.

그들의 전법서에 따르면 폴리매스 문명의 군대는 정확한 직사각형 모양의 방진으로 이루어져 있었다고 합니다. 즉 $X$행 $Y$열의 직사각형을 정확히 $XY$명의 병사가 채우고 있는 형태인 것입니다. 병사의 수가 정확히 떨어지지 않아 몇 명이 남거나 부족한 경우는 허용되지 않았습니다.

또한 폴리매스 문명은 본래 강력한 군사력으로 주변의 약소국을 다수 복속시켰으므로 군대에도 서로 다른 $N$개의 민족이 섞여 있었습니다. 특히, 1차 동아전쟁에 참가한 병사들 중 $i$번째 민족 출신인 병사는 정확히 $A\_i$명이었다는 기록이 남아 있습니다.

폴리매스 문명에서는 출신 민족에 따라 시민들을 차별대우했는데 군대 또한 이 영향을 받았습니다. 특히 $i\<j$일 때 $i$번째 민족 출신인 병사는 항상 $j$번째 민족 출신인 병사보다 앞에 서야 했습니다. 이 때 $a$행 $b$열에 위치한 병사가 $a'$행 $b'$열에 위치한 병사보다 앞에 선다는 말은 다음 둘 중 하나가 성립함을 의미합니다.

• $a < a'$
• $a=a'$이고 $b\<b'$

그러나 이 방식에는 약간의 문제가 있었는데, 서로 다른 민족인 병사끼리 양옆으로 인접해 있다면 항상 싸움이 벌어진다는 것이었습니다. 이 때 $a$행 $b$열에 위치한 병사와 $a'$행 $b'$열에 위치한 병사가 양옆으로 인접해 있다는 말은 $a=a'$이고 $|b-b'|=1$임을 뜻합니다.

폴리매스 문명의 육군 장교들은 싸움을 막기 위해 평화의 돌을 사용했습니다. 평화의 돌의 힘을 사용하면 서로 다른 민족인 병사가 인접해 있더라도 싸움이 나는 것을 막을 수 있지만, 한 개의 돌 당 하나의 싸움밖에 막을 수 없습니다. 즉 평화의 돌을 $k$개 가지고 있다면 민족이 다르고 서로 인접한 병사의 쌍이 $k$쌍 이하여야 싸움이 일어나지 않는 것입니다.

당신은 여러 기록들을 통해 폴리매스 문명의 장교들은 방진이 옆으로 넓을수록, 즉 $Y$가 최대한 클수록 군대가 강하다고 생각했다는 사실을 밝혀냈습니다. 따라서 당신은 1차 동아전쟁에 사용된 방진 또한 완벽한 직사각형 모양이고 싸움이 일어나지 않는 형태의 방진 중 가장 큰 $Y$값을 가지는 방진일 것이라고 추측하고 있습니다. 그러나 당신은 아직 폴리매스 문명이 정확히 몇 개의 평화의 돌을 가지고 있었는지는 밝혀내지 못했기 때문에, $0 \le k \le N-1$인 모든 정수 $k$에 대해서 가능한 $Y$의 최댓값을 모두 구하기로 했습니다.

첫 줄에 민족의 수 $N$이 주어집니다.

다음 줄에는 각 민족의 병사의 수 $A\_1, A\_2, \cdots, A\_N$이 주어집니다.

첫 줄에 $0 \le k \le N-1$에 대해 가능한 $Y$의 최댓값을 각각 공백으로 구분하여 출력합니다.

• $1 \le N \le 10^6$
• $1 \le A\_i \le 10^{18}$
• $M \le 10^{18}$ (단, $M = \sum\_{i=1}^N A\_i$)