#include "bits/stdc++.h"
using namespace std;

using ll = int64_t;

using vl = vector<ll>;

#define ice(i, a, b) for (int (i) = (a); (i) < (b); ++(i))
#define fire(i, a, b) for (int (i) = (b) - 1; (i) >= (a); --(i))

ll n;

ll get(vl& w, ll idx) {
    ll s = 0;
    while (idx > 0) {
        s += w[idx];
        idx -= idx & (-idx);
    }
    return s;
}

void upd(vl& w, ll idx, ll val) {
    while (idx <= n) {
        w[idx] += val;
        idx += idx & (-idx);
    }
}

ll cnt(vl v) {
    ll ans = 0;
    vl w(n + 1, 0);
    fire(i, 0, n) {
        ans += get(w, v[i]);
        upd(w, v[i] + 1, 1);
    }
    return ans;
}

void solve() {
    cin >> n;
    vl v(n);
    ice(i, 0, n) {
        cin >> v[i];
    }
    ll ans = cnt(v);
    cout << ans << '\n';
    ice(i, 0, n - 1) {
        ans += ((n - 1) - 2 * v[i]);
        cout << ans << '\n';
    }
}

int main() {
    int tc = 1;
    ice(i, 0, tc) {
        solve();
    }
}
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using Pii = pair<int, int>;
const ll MOD = 1000000007;
const ll MOD3 = 998244353;
const ll INFl = 10000000000000000;
const int INFi = 1000000000;

int main() {
    int n;cin >> n;
    int sum = 0;
    vector<int> t(n);
    rep(i, n) {

        cin >> t[i];
        sum += t[i];
    }

    int ans = 10000000;

    vector<vector<bool>> dp(n + 1,  vector<bool>(100010, false));

    // rep(i, 100001) dp[0][i] = 0;
    dp[0][0] = 1;

    rep(i, n + 1) {
        // cout << i << endl;
        rep(j, 100001) {
            if(i == 0) break;
            dp[i][j] = dp[i - 1][j];
            if(j - t[i - 1] < 0) continue;
            // dp[i][j] = max(dp[i][j], dp[i - 1][j - t[i]]);
            if(dp[i][j - t[i - 1]]) dp[i][j] = dp[i - 1][j - t[i - 1]];
        }
    }


    for(int i = (sum + 1) / 2;i <= sum;i++) {
        if(dp[n][i]) {
            cout << i << endl;
            return 0;
        }
    }



    // rep(i, 1 << n) {
    //     int a1 = 0, a2 =0;

    //     rep(j, n) {
    //         if(i  & 1 << j) {
    //             a1 += t[j];
    //         }
    //         else a2 += t[j];
    //     }     

    //     ans = min(max(a1, a2), ans);
    // }

    // // cout << ans << endl
    // cout << sum / n << endl;
    // // cout << sum << endl;
    // // int ave = sum / n;

    // // int a1 = t[0] - ave;    
    // // int a2 = 0;

    // // rep(i, n) {

    // //     rep(j, n) {

    // //     }

    // // }
}