전쟁 준비하기

폴리매스 왕국은 이웃 나라 사이언스보드를 정복하려고 전쟁을 준비한다. 당신은 전쟁에 쓸 방진을 짜 달라는 부탁을 받고 방진을 연구하고 있다.

전쟁 지역의 지형을 고려하면 가장 효율적인 방진은 직사각형 구조다. 즉 $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$)