#include #define rep(i, a, n) for(int i = a; i < n; i++) #define repr(i, a, b) for(int i = a; i >= b; i--) #define int long long #define all(a) a.begin(), a.end() #define chmax(x, y) x = max(x, y) #define chmin(x, y) x = min(x, y) using namespace std; typedef pair P; const int mod = 1000000007; const int INF = 1e12; struct BIT{ int N; vector dat; BIT() {} BIT(int n) { N = n; dat.resize(N + 1); } // update k th element (0-index) void add(int k, int x){ k++; while(k <= N){ dat[k] += x; k += k&-k; } } // sum [0, k) (0-index) int sum(int k){ int s = 0; while(k > 0){ s += dat[k]; k -= k&-k; } return s; } // sum [a, b) (0-index) int query(int a, int b){ return sum(b) - sum(a); } }; int n; int calc(vector &a){ int res = 0; BIT bit(n); for(int j = 0; j < n; j++){ int tmp = j - bit.sum(a[j]); res += tmp; cout << tmp << endl; bit.add(a[j], 1); } return res; } struct CumulativeSum{ vector data; CumulativeSum(int sz) : data(sz, 0) {}; void add(int k, int x){ data[k] += x; } void build(){ for(int i = 1; i < data.size(); i++){ data[i] += data[i - 1]; } } //区間[0,k]の和 int query(int k){ if(k < 0) return 0; return (data[min(k, (int)data.size() - 1)]); } //区間[l.r)の和 int query(int l, int r){ return query(r - 1) - query(l - 1); } }; signed main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n; vector a(n); rep(i, 0, n) cin >> a[i]; vector b = a; sort(all(b)); b.erase(unique(all(b)), b.end()); rep(i, 0, n){ a[i] = lower_bound(all(b), a[i]) - b.begin(); } CumulativeSum s(n); rep(i, 0, n) s.add(a[i], 1); s.build(); int res = 0; BIT bit(n); for(int j = 0; j < n; j++){ int tmp = j - bit.sum(a[j]); res += tmp; bit.add(a[j], 1); } cout << res << endl; for(int j = 0; j < n - 1; j++){ int tmp = n - 2 * s.query(a[j]) + 1; res += tmp; cout << res << endl; } }