import bisect def main(): import sys input = sys.stdin.read data = input().split() n = int(data[0]) P = list(map(int, data[1:n+1])) INF = float('inf') # Precompute cnt and sum_cnt cnt = [[0] * (n + 1) for _ in range(n + 1)] sum_cnt = [[0] * (n + 1) for _ in range(n + 1)] for l in range(1, n + 1): if l == 1: S = [] else: if l == 2: S = [P[0]] else: pos = bisect.bisect_left(S, P[l - 2]) S.insert(pos, P[l - 2]) # Compute cnt[l][i] for all i for i in range(1, n + 1): if i < l: cnt_l_i = 0 else: x = P[i - 1] pos = bisect.bisect_right(S, x) cnt_l_i = len(S) - pos cnt[l][i] = cnt_l_i # Compute sum_cnt[l][r] sum_so_far = 0 for r in range(1, n + 1): if r >= l: sum_so_far += cnt[l][r] sum_cnt[l][r] = sum_so_far # Initialize DP dp = [[INF] * (n + 1) for _ in range(n + 2)] for i in range(1, n + 1): dp[1][i] = 0 for k in range(2, n + 1): for i in range(1, n + 1): if i < k: dp[k][i] = INF continue min_val = INF # j can be from (k-1) to (i-1) for j in range(k - 1, i): if dp[k - 1][j] == INF: continue current = dp[k - 1][j] + sum_cnt[j + 1][i] if current < min_val: min_val = current dp[k][i] = min_val if min_val != INF else INF # Output the results for k in range(1, n + 1): print(dp[k][n] if dp[k][n] != INF else 0) if __name__ == '__main__': main()