사하르나의 계단

몰도바의 사하르나(Saharna)는 동굴과 폭포로 이름난 아름다운 명소로, 그곳에서는 다양한 모양과 크기의 돌을 찾을 수 있다. 중세 시대에는 이 돌들로 요새의 계단을 쌓았으며, 계단의 각 단은 원칙적으로 돌 하나로 만들어졌다.

돌은 무거워서 정해진 순서대로 한 줄로 고정되어 놓여 있다. 각 돌의 높이는 알려져 있어, 정수 수열 $H = (h_1, h_2, \dots, h_i, \dots, h_n)$ 로 주어진다. 여기서 $h_i$ 는 $i$ 번째 돌의 높이이다.

계단을 만들 때 장인은 돌들을 놓인 순서대로 훑으면서 각 단에 쓸 돌을 하나씩 고른다. 단, 새로 고르는 돌의 높이는 바로 직전에 고른 돌의 높이보다 낮아서는 안 된다. 즉, 하나의 계단은 (원래 순서를 유지하는) 높이가 비내림차순인 부분수열이다.

예를 들어 $H = (1, 3, 4, 2, 3, 4, 1, 2, 2, 3, 3, 2)$ 일 때, 아래에서 밑줄 친 돌들로 하나의 계단을 만들 수 있다.

$H = (\underline{1}, 3, 4, \underline{2}, 3, 4, 1, \underline{2}, \underline{2}, \underline{3}, \underline{3}, 2)$

돌을 더 많이 쓸수록 더 좋은 성을 지을 수 있으므로, 장인은 가능한 한 많은 돌을 사용하려 한다.

$L(H, k)$ 를, 각각 최소 한 단 이상을 가지며 서로 겹치지 않게 돌을 나누어 쓰는 $k$ 개의 계단에 사용할 수 있는 돌의 최대 개수라고 정의한다.

위 예시에서 $L(H, 1) = 6$ 이며, 밑줄 친 돌들이 최적의 계단 하나를 이룬다.

마찬가지로 $L(H, 2) = 9$ 임을 확인할 수 있다. 아래 그림에서 첫 번째 계단의 돌은 한 줄 밑줄($\underline{\ }$), 두 번째 계단의 돌은 두 줄 밑줄($\underline{\underline{\ }}$)로 표시했다.

$H = (\underline{1}, \underline{\underline{3}}, \underline{\underline{4}}, \underline{2}, 3, \underline{\underline{4}}, 1, \underline{2}, \underline{2}, \underline{3}, \underline{3}, 2)$

$k = 2$ 일 때 첫 번째 계단에는 6개, 두 번째 계단에는 3개의 돌이 쓰인다.

계단을 3개 만들 때 사용할 수 있는 돌의 최대 개수는 아래와 같다.

$H = (\underline{1}, \underline{\underline{\underline{3}}}, \underline{\underline{\underline{4}}}, \underline{2}, \underline{3}, \underline{\underline{\underline{4}}}, \underline{\underline{1}}, \underline{\underline{2}}, \underline{\underline{2}}, \underline{3}, \underline{3}, \underline{\underline{2}})$

세 줄 밑줄은 세 번째 계단을 나타내며, 나머지 표시는 앞과 같은 의미이다. 따라서 $L(H, 3) = 12$ 이다. $k = 3$ 일 때 첫 번째 계단에 5개, 두 번째 계단에 4개, 세 번째 계단에 3개의 돌이 쓰인다. $k = 3$ 에서 고른 첫 번째·두 번째 계단은 $k = 1, 2$ 일 때 고른 계단과 다를 수 있음에 유의하라.

$k$ 를 $1, 2, 3, \dots$ 으로 늘려 가면 어떤 값 $q$ 에서 $L(H, q) = n$ 이 된다. 여기서 $n$ 은 돌의 총 개수이다.

주어진 높이 수열 $H$ 에 대해 $k = 1, 2, \dots, q$ 각각에 대한 $L(H, k)$ 를 계산하는 프로그램을 작성하라.

첫째 줄에 양의 정수 $n$ 이 주어진다. 둘째 줄에 $n$ 개의 양의 정수 $h_1, h_2, \dots, h_n$ 이 공백으로 구분되어 주어진다.

$q$ 개의 줄을 출력한다. $k$ 번째 줄에는 $L(H, k)$ 의 값을 출력한다($k = 1, 2, \dots, q$). 여기서 $q$ 는 $L(H, q) = n$ 을 만족하는 가장 작은 값이다.

• $1 \le n \le 5000$
• $1 \le h_i \le 255,\ i = 1, 2, \dots, n$