K Integers

You are given a permutation $p_1, p_2, \ldots, p_n$.

In one move you can swap two adjacent values.

You want to perform a minimum number of moves, such that in the end there will exist a subsegment $1,2,\ldots, k$, in other words in the end there should be an integer $i$, $1 \leq i \leq n-k+1$ such that $p_i = 1, p_{i+1} = 2, \ldots, p_{i+k-1}=k$.

Let $f(k)$ be the minimum number of moves that you need to make a subsegment with values $1,2,\ldots,k$ appear in the permutation.

You need to find $f(1), f(2), \ldots, f(n)$.Input

The first line of input contains one integer $n$ ($1 \leq n \leq 200\,000$): the number of elements in the permutation.

The next line of input contains $n$ integers $p_1, p_2, \ldots, p_n$: given permutation ($1 \leq p_i \leq n$).Output

Print $n$ integers, the minimum number of moves that you need to make a subsegment with values $1,2,\ldots,k$ appear in the permutation, for $k=1, 2, \ldots, n$.Examplesinput

5
5 4 3 2 1

output

0 1 3 6 10 

input

3
1 2 3

output

0 0 0 

Solution:

#include <bits/stdc++.h>

using namespace std;

template <typename T>
class fenwick {
public:
vector<T> fenw;
int n;

fenwick(int _n) : n(_n) {
fenw.resize(n);
}

void modify(int x, T v) {
while (x < n) {
      fenw[x] += v;
      x |= (x + 1);
    }
  }

  T get(int x) {
    T v{};
    while (x >= 0) {
v += fenw[x];
x = (x & (x + 1)) - 1;
}
return v;
}
};

class segtree {
public:
struct node {
// don't forget to set default value (used for leaves)
// not necessarily neutral element!
long long L = 0;
long long R = 0;
int alive = 1;
int addL = 0;
int addR = 0;

void apply(int l, int r) {
alive = 0;
L = R = 0;
addL = addR = 0;
}

void apply(int l, int r, int v, char c) {
if (c == 'L') {
L += (long long) alive * v;
addL += v;
}
if (c == 'R') {
R += (long long) alive * v;
addR += v;
}
}
};

node unite(const node &a, const node &b) const {
node res;
res.L = a.L + b.L;
res.R = a.R + b.R;
res.alive = a.alive + b.alive;
return res;
}

inline void push(int x, int l, int r) {
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    if (tree[x].addL != 0) {
      tree[x + 1].apply(l, y, tree[x].addL, 'L');
      tree[z].apply(y + 1, r, tree[x].addL, 'L');
      tree[x].addL = 0;
    }
    if (tree[x].addR != 0) {
      tree[x + 1].apply(l, y, tree[x].addR, 'R');
      tree[z].apply(y + 1, r, tree[x].addR, 'R');
      tree[x].addR = 0;
    }
  }

  inline void pull(int x, int z) {
    tree[x] = unite(tree[x + 1], tree[z]);
  }

  int n;
  vector<node> tree;

void build(int x, int l, int r) {
if (l == r) {
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }

  template <typename M>
void build(int x, int l, int r, const vector<M> &v) {
if (l == r) {
tree[x].apply(l, r, v[l]);
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v);
    build(z, y + 1, r, v);
    pull(x, z);
  }

  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tree[x];
    }
    int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
res = get(z, y + 1, r, ll, rr);
} else {
res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
}
}
pull(x, z);
return res;
}

template <typename... M>
void modify(int x, int l, int r, int ll, int rr, const M&... v) {
if (ll <= l && r <= rr) {
      tree[x].apply(l, r, v...);
      return;
    }
    int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      modify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
modify(z, y + 1, r, ll, rr, v...);
}
pull(x, z);
}

int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
if (l == r) {
return l;
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[x + 1])) {
      res = find_first_knowingly(x + 1, l, y, f);
    } else {
      res = find_first_knowingly(z, y + 1, r, f);
    }
    pull(x, z);
    return res;
  }

  int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_first_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (ll <= y) {
      res = find_first(x + 1, l, y, ll, rr, f);
    }
    if (rr > y && res == -1) {
res = find_first(z, y + 1, r, ll, rr, f);
}
pull(x, z);
return res;
}

int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
if (l == r) {
return l;
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[z])) {
      res = find_last_knowingly(z, y + 1, r, f);
    } else {
      res = find_last_knowingly(x + 1, l, y, f);
    }
    pull(x, z);
    return res;
  }

  int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_last_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (rr > y) {
res = find_last(z, y + 1, r, ll, rr, f);
}
if (ll <= y && res == -1) {
      res = find_last(x + 1, l, y, ll, rr, f);
    }
    pull(x, z);
    return res;
  }

  segtree(int _n) : n(_n) {
    assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1);
}

template <typename M>
segtree(const vector<M> &v) {
n = v.size();
assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1, v);
}

node get(int ll, int rr) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }

  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }

  template <typename... M>
void modify(int ll, int rr, const M&... v) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
    modify(0, 0, n - 1, ll, rr, v...);
  }

  // find_first and find_last call all FALSE elements
  // to the left (right) of the sought position exactly once

  int find_first(int ll, int rr, const function<bool(const node&)> &f) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_first(0, 0, n - 1, ll, rr, f);
  }

  int find_last(int ll, int rr, const function<bool(const node&)> &f) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_last(0, 0, n - 1, ll, rr, f);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
vector<int> p(n);
for (int i = 0; i < n; i++) {
    cin >> p[i];
--p[i];
}
vector<int> pos(n);
for (int i = 0; i < n; i++) {
    pos[p[i]] = i;
  }
  fenwick<int> fenw(n);
vector<long long> res(n);
long long inv = 0;
segtree st(n);
for (int it = 0; it < n; it++) {
    int at = pos[it];
    inv += fenw.get(n - 1) - fenw.get(at);
    fenw.modify(at, +1);
    if (at > 0) {
st.modify(0, at - 1, 1, 'R');
}
if (at < n - 1) {
      st.modify(at + 1, n - 1, 1, 'L');
    }
    st.modify(at, at);
    int med = -1;
    {
      int low = 0, high = n - 1;
      while (low < high) {
        int mid = (low + high) >> 1;
int s = fenw.get(mid);
if (s >= it / 2 + 1) {
high = mid;
} else {
low = mid + 1;
}
}
med = low;
}
res[it] = inv;
if (med > 0) {
res[it] += st.get(0, med - 1).L;
}
if (med < n - 1) {
      res[it] += st.get(med + 1, n - 1).R;
    }
  }
  for (int i = 0; i < n; i++) {
    if (i > 0) {
cout << " ";
    }
    cout << res[i];
  }
  cout << '\n';
  return 0;
}