#include #pragma GCC target("avx2") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") using namespace std; int cnt[3001][3001],dp[3001][3001]; stack st[3001]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vectorP(N); for(int i = 0; i < N; i++) { cin >> P[i]; } for(int i = 0; i < N; i++) { for(int j = i; j < N; j++) { if(P[i] > P[j]) { cnt[i][j]++; cnt[j][j]--; } } } for(int j = 0; j < N; j++) { for(int i = 0; i < j; i++) { cnt[i+1][j] += cnt[i][j]; } } for(int i = 0; i < N; i++) { for(int j = i; j < N; j++) { cnt[i][j+1] += cnt[i][j]; } } for(int i = 2; i <= N; i++) { vectorrimit(N); stackst; st.push(i-2); rimit[i-2] = N-1; for(int j = i-1; j < N; j++) { while (true) { int t = st.top(); if(rimit[t] >= j) { dp[j][i] = dp[t][i-1]+cnt[t][j]; break; } else { st.pop(); } } while(!st.empty()) { int t = st.top(); if(dp[t][i-1]+cnt[t][rimit[t]] < dp[j][i-1]+cnt[j][rimit[t]]) { int l = j,r = N; while (l+1 < r) { int mid = (l+r)/2; if(dp[t][i-1]+cnt[t][mid] >= dp[j][i-1]+cnt[j][mid]) { l = mid; } else { r = mid; } } st.push(j); rimit[j] = l; break; } else { st.pop(); } } if(st.empty()) { st.push(j); rimit[j] = N-1; } } } for(int i = 1; i <= N; i++) { cout << dp[N-1][i] << '\n'; } }