언덕

이노폴리스시에 오신 것을 환영합니다. 일 년 내내 이노폴리스 시민들은 끝없는 도시 공사를 견뎌야 합니다.

방 창문에서 언덕 n개의 수열이 보이고, i번째 언덕의 높이는 ai입니다. 이노폴리스 시청은 언덕 위에 집을 짓고자 합니다. 그러나 도시 미관을 위해 집은 이웃한 언덕(존재하는 경우)보다 엄격히 높은 언덕에만 지을 수 있습니다. 예를 들어 높이 수열이 5, 4, 6, 2라면 높이 5인 언덕과 6인 언덕에만 집을 지을 수 있습니다.

이노폴리스 시청에는 굴착기가 있고, 한 시간에 임의의 언덕 높이를 1만큼 낮출 수 있습니다. 굴착기는 한 번에 한 언덕에서만 작업할 수 있습니다. 언덕 높이를 0까지 낮추거나 음수로 만드는 것도 허용됩니다. 어떤 언덕의 높이를 높이는 것은 불가능합니다. 시청은 집 k채를 지으려 하므로, 위 조건을 만족하는 언덕이 최소 k개 있어야 합니다. 시청의 계획을 이루기 위해 언덕을 조정하는 데 필요한 최소 시간은 얼마입니까?

그런데 k의 정확한 값은 아직 정해지지 않았으므로, 1 ≤ k ≤ ⌈n/2⌉ 범위의 모든 k에 대한 답을 계산해 주시겠습니까? 여기서 ⌈n/2⌉는 n을 2로 나눈 값을 올림한 것입니다.

첫째 줄에는 수열에 있는 언덕의 개수 n (1 ≤ n ≤ 5000)이 주어집니다. 둘째 줄에는 수열에 있는 언덕의 높이 n개 ai (1 ≤ ai ≤ 100 000)가 주어집니다.

공백으로 구분된 ⌈n/2⌉개의 수를 출력합니다. i번째로 출력하는 수는 집 i채를 지을 수 있도록 언덕을 고르는 데 필요한 최소 시간이어야 합니다.

첫 번째 예제에서, 지을 수 있는 언덕을 최소 하나 얻으려면 두 번째 언덕을 한 시간 동안 1만큼 낮추면 됩니다. 그러면 높이 수열이 1, 0, 1, 1, 1이 되고 첫 번째 언덕이 지을 수 있는 언덕이 됩니다.

첫 번째 예제에서, 지을 수 있는 언덕을 최소 둘 또는 최소 셋 얻으려면 두 번째 언덕과 네 번째 언덕을 낮추면 됩니다. 그러면 높이 수열이 1, 0, 1, 0, 1이 되고 1, 3, 5번째 언덕이 지을 수 있는 언덕이 됩니다.