#include using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) template //T : dat[]の中身の型 class segtree{ public: int n; T neutral; vector dat; T func(T l, T r){ //区間をマージする関数 return l + r; } segtree(int n_, T val): n(n_), neutral(val){ //n_:要素数 val:単位元 n = 1; while(n < n_) n *= 2; dat.resize(n * 2, neutral); //初期値 } void update(int k, T val){ // k番目の値(0-indexed)を val に変更 for (dat[k += n] = val; k > 0; k >>= 1){ // kを含む区間のインデックスを下から順に列挙 dat[k>>1] = func(dat[k], dat[k ^ 1]); } } T query(int l, int r){ //[l, r)の区間 /* 可換出ない時危険 */ T ret = neutral; for (l += n, r += n; l < r; l >>= 1, r >>= 1){ if(l & 1) ret = func(ret, dat[l++]); if(r & 1) ret = func(ret, dat[--r]); } return ret; } }; int main(int argc, char const *argv[]) { int n; cin >> n; vector _a(n), tmpa(n), sorta(n); rep(i, n) cin >> _a[i]; rep(i, n) tmpa[i] = _a[i], sorta[i] = _a[i]; sort(tmpa.begin(), tmpa.end()); sort(sorta.begin(), sorta.end()); tmpa.erase(unique(tmpa.begin(), tmpa.end()), tmpa.end()); vector a(n); rep(i, n) a[i] = lower_bound(tmpa.begin(), tmpa.end(), _a[i]) - tmpa.begin() + 1; // rep(i, n) printf("%d ", a[i]); // printf("\n"); segtree seg(n + 10, 0); int cnt0 = 0; rep(i, n) { cnt0 += seg.query(a[i] + 1, n + 1); seg.update(a[i], 1); } // printf("cnt0 %d\n", cnt0); vector cnt(n); cnt[0] = cnt0; reps(i, 1, n) { int d1 = lower_bound(sorta.begin(), sorta.end(), a[i - 1]) - sorta.begin(); int d2 = n - (upper_bound(sorta.begin(), sorta.end(), a[i - 1]) - sorta.begin()); cnt[i] = cnt[i - 1] - d1 + d2; } for(auto u : cnt) printf("%d\n", u); return 0; }