#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n;
long long a[N], id[N];
pair<long long, long long> G[N];
void Upd(int x, int y) {
  while (x <= n) {
    G[x].first++;
    G[x].second += y;
    x += (x & -x);
  }
}
pair<long long, long long> Get(int x) {
  pair<long long, long long> res;
  res.first = res.second = 0;
  while (x > 0) {
    res.first += G[x].first;
    res.second += G[x].second;
    x -= (x & -x);
  }
  return res;
}
int main() {
  scanf("%lld", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
    id[a[i]] = i;
  }
  long long inv = 0;
  for (int i = 1; i <= n; i++) {
    long long idx = id[i], ans = 0;
    inv += Get(n).first - Get(idx).first;
    ans = inv;
    Upd(idx, idx);
    long long l = 1, r = n, mid, res = -1;
    while (l <= r) {
      mid = (l + r) / 2;
      if (Get(mid).first >= (i + 1) / 2) {
        res = mid;
        r = mid - 1;
      } else
        l = mid + 1;
    }
    long long totR = res + Get(n).first - Get(res).first;
    ans += Get(n).second - Get(res).second -
           (totR * (totR + 1) / 2 - res * (res + 1) / 2);
    long long totL = res - Get(res - 1).first;
    ans += (res - 1) * res / 2 - (totL - 1) * totL / 2 - Get(res - 1).second;
    printf("%lld ", ans);
  }
}

### Prompt

In cpp, your task is to solve the following problem:

You are given a permutation p_1, p_2, …, 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,…, k, in other words in the end there should be an integer i, 1 ≤ i ≤ n-k+1 such that p_i = 1, p_{i+1} = 2, …, 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,…,k appear in the permutation.

You need to find f(1), f(2), …, f(n).

Input

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

The next line of input contains n integers p_1, p_2, …, p_n: given permutation (1 ≤ p_i ≤ n).

Output

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

Examples

Input


5
5 4 3 2 1


Output


0 1 3 6 10 


Input


3
1 2 3


Output


0 0 0 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n;
long long a[N], id[N];
pair<long long, long long> G[N];
void Upd(int x, int y) {
  while (x <= n) {
    G[x].first++;
    G[x].second += y;
    x += (x & -x);
  }
}
pair<long long, long long> Get(int x) {
  pair<long long, long long> res;
  res.first = res.second = 0;
  while (x > 0) {
    res.first += G[x].first;
    res.second += G[x].second;
    x -= (x & -x);
  }
  return res;
}
int main() {
  scanf("%lld", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
    id[a[i]] = i;
  }
  long long inv = 0;
  for (int i = 1; i <= n; i++) {
    long long idx = id[i], ans = 0;
    inv += Get(n).first - Get(idx).first;
    ans = inv;
    Upd(idx, idx);
    long long l = 1, r = n, mid, res = -1;
    while (l <= r) {
      mid = (l + r) / 2;
      if (Get(mid).first >= (i + 1) / 2) {
        res = mid;
        r = mid - 1;
      } else
        l = mid + 1;
    }
    long long totR = res + Get(n).first - Get(res).first;
    ans += Get(n).second - Get(res).second -
           (totR * (totR + 1) / 2 - res * (res + 1) / 2);
    long long totL = res - Get(res - 1).first;
    ans += (res - 1) * res / 2 - (totL - 1) * totL / 2 - Get(res - 1).second;
    printf("%lld ", ans);
  }
}

```