```go
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	n, _ := strconv.Atoi(scanner.Text())
	scanner.Scan()
	line := strings.Fields(scanner.Text())
	a := make([]int, n+2)
	for i := 1; i <= n; i++ {
		a[i], _ = strconv.Atoi(line[i-1])
	}

	m := (n + 1) / 2
	ans := make([]int, m+1)
	INF := 1000000000

	prev_dp := make([]int, n+1)
	prev_pref := make([]int, n+1)
	cur_dp := make([]int, n+1)
	cur_pref := make([]int, n+1)

	for i := 1; i <= n; i++ {
		c := 0
		if i > 1 {
			c += max(0, a[i-1]-a[i]+1)
		}
		if i < n {
			c += max(0, a[i+1]-a[i]+1)
		}
		cur_dp[i] = c
		if i == 1 {
			cur_pref[i] = c
		} else {
			cur_pref[i] = min(cur_pref[i-1], c)
		}
	}
	ans[1] = cur_pref[n]
	prev_dp, cur_dp = cur_dp, make([]int, n+1)
	prev_pref, cur_pref = cur_pref, make([]int, n+1)

	for j := 2; j <= m; j++ {
		for i := 1; i <= n; i++ {
			if i < 2*j-1 {
				cur_dp[i] = INF
			} else {
				c := 0
				if i > 1 {
					c += max(0, a[i-1]-a[i]+1)
				}
				if i < n {
					c += max(0, a[i+1]-a[i]+1)
				}
				best := INF
				if i-3 >= 1 {
					best = min(best, prev_pref[i-3])
				}
				if i-2 >= 1 && prev_dp[i-2] != INF {
					left := max(0, a[i-1]-a[i-2]+1)
					right := max(0, a[i-1]-a[i]+1)
					overlap := min(left, right)
					best = min(best, prev_dp[i-2]-overlap)
				}
				if best != INF {
					cur_dp[i] = c + best
				} else {
					cur_dp[i] = INF
				}
			}
			if i == 1 {
				cur_pref[i] = cur_dp[i]
			} else {
				cur_pref[i] = min(cur_pref[i-1], cur_dp[i])
			}
		}
		ans[j] = cur_pref[n]
		prev_dp, cur_dp = cur_dp, make([]int, n+1)
		prev_pref, cur_pref = cur_pref, make([]int, n+1)
	}

	for j := m; j >= 1; j-- {
		if j < m && ans[j+1] < ans[j] {
			ans[j] = ans[j+1]
		}
	}

	out := make([]string, m)
	for i := 1; i <= m; i++ {
		out[i-1] = strconv.Itoa(ans[i])
	}
	fmt.Println(strings.Join(out, " "))
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
```