21558번 - 전쟁 준비하기 서브태스크

이번에 폴리매스 왕국은 이웃 나라인 사이언스보드를 정복하기 위해 전쟁을 치르려고 합니다. 당신은 전쟁에서 사용할 방진을 짜 달라는 부탁을 받아 방진을 연구하고 있습니다.

전쟁 지역의 지형상 가장 효율적인 방진은 직사각형 구조일 것으로 보입니다. 즉 $X$행 $Y$열의 직사각형을 정확히 $XY$명의 병사가 채우고 있는 형태를 말합니다. 병사의 수가 정확히 떨어지지 않아 몇 명이 남거나 부족한 경우에는 이러한 방진을 짤 수 없습니다.

폴리매스 문명은 예전에도 강력한 군사력으로 주변의 약소국을 다수 복속시켰으므로, 군대에도 서로 다른 $N$개의 민족이 섞여 있습니다. 특히, 이번 전쟁에 참가하게 될 병사들 중 $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$가 최대한 클수록 군대가 강하다고 생각합니다. 따라서 당신은 위 조건을 만족하는 방진 중 가장 큰 $Y$값을 가지는 방진을 찾아내야 합니다. 그러나 평화의 돌에 관련된 정보는 왕국의 기밀 사항이기 때문에, 당신은 정확히 몇 개의 평화의 돌이 있는지 알지 못합니다. 따라서 당신은 $0 \le k \le N-1$인 모든 정수 $k$에 대해서 가능한 $Y$의 최댓값을 모두 구하기로 했습니다.

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

다음 줄에는 각 민족의 병사 수 $A_1, A_2, \cdots, A_N$이 주어집니다.

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

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