import sys sys.setrecursionlimit(1 << 25) def main(): import sys input = sys.stdin.read data = input().split() N = int(data[0]) P = list(map(int, data[1:N+1])) original_inversion = 0 class FenwickTree: def __init__(self, size): self.size = size self.tree = [0]*(size + 2) def update(self, index, delta=1): while index <= self.size: self.tree[index] += delta index += index & -index def query(self, index): res = 0 while index > 0: res += self.tree[index] index -= index & -index return res max_p = max(P) ft = FenwickTree(max_p) for i in reversed(range(N)): original_inversion += ft.query(P[i] - 1) ft.update(P[i]) cross = [[0]*(N+2) for _ in range(N+2)] for k in range(0, N+1): ft = FenwickTree(max_p) for x in P[:k]: ft.update(x) current = 0 cross[k][k] = 0 for i in range(k+1, N+1): v = P[i-1] count = ft.query(max_p) - ft.query(v) current += count cross[k][i] = current dp = [[float('inf')]*(N+2) for _ in range(N+2)] for i in range(1, N+1): dp[1][i] = 0 for j in range(2, N+1): for i in range(j, N+1): for k in range(j-1, i): if dp[j-1][k] + cross[k][i] < dp[j][i]: dp[j][i] = dp[j-1][k] + cross[k][i] for k in range(1, N+1): print(dp[k][N]) if __name__ == "__main__": main()