#include <bits/stdc++.h>
using namespace std;
const long long maxn = 1e5 + 5;
const long long MAXN = 1e6 + 5;
long long n, m, t;
long long a[MAXN];
long long tree1[MAXN], tree2[MAXN];
long long pos[MAXN];
void add(long long *tree, long long x, long long xx) {
  while (x <= n) tree[x] += xx, x += (x & (-x));
}
long long query(long long *tree, long long x) {
  long long sum = 0;
  while (x > 0) sum += tree[x], x -= (x & (-x));
  return sum;
}
long long bs(long long x) {
  long long l = 1, r = n;
  long long ans;
  while (l <= r) {
    long long mid = l + r >> 1;
    if (query(tree1, mid) > x / 2)
      ans = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  return ans;
}
int main() {
  cin >> n;
  for (long long i = 1; i <= n; i++) scanf("%d", &a[i]), pos[a[i]] = i;
  long long cnt = 0;
  for (long long i = 1; i <= n; i++) {
    long long ans = 0;
    add(tree1, pos[i], 1);
    add(tree2, pos[i], pos[i]);
    cnt += query(tree1, n) - query(tree1, pos[i]);
    long long tmp = bs(i);
    long long a = i / 2, b = i - a - 1;
    ans += a * tmp - query(tree2, tmp - 1) - (a + 1) * a / 2;
    long long tmpp = query(tree2, n) - query(tree2, tmp);
    ans += tmpp - b * tmp - (b + 1) * b / 2;
    cout << ans + cnt << ' ';
  }
}

### Prompt

Generate a CPP solution to 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 long long maxn = 1e5 + 5;
const long long MAXN = 1e6 + 5;
long long n, m, t;
long long a[MAXN];
long long tree1[MAXN], tree2[MAXN];
long long pos[MAXN];
void add(long long *tree, long long x, long long xx) {
  while (x <= n) tree[x] += xx, x += (x & (-x));
}
long long query(long long *tree, long long x) {
  long long sum = 0;
  while (x > 0) sum += tree[x], x -= (x & (-x));
  return sum;
}
long long bs(long long x) {
  long long l = 1, r = n;
  long long ans;
  while (l <= r) {
    long long mid = l + r >> 1;
    if (query(tree1, mid) > x / 2)
      ans = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  return ans;
}
int main() {
  cin >> n;
  for (long long i = 1; i <= n; i++) scanf("%d", &a[i]), pos[a[i]] = i;
  long long cnt = 0;
  for (long long i = 1; i <= n; i++) {
    long long ans = 0;
    add(tree1, pos[i], 1);
    add(tree2, pos[i], pos[i]);
    cnt += query(tree1, n) - query(tree1, pos[i]);
    long long tmp = bs(i);
    long long a = i / 2, b = i - a - 1;
    ans += a * tmp - query(tree2, tmp - 1) - (a + 1) * a / 2;
    long long tmpp = query(tree2, n) - query(tree2, tmp);
    ans += tmpp - b * tmp - (b + 1) * b / 2;
    cout << ans + cnt << ' ';
  }
}

```