题目描述

小张拿到了一个排列，他定f(i)为：将第i个元素取反后，形成的数组的逆序对数量。小张希望你求出到的值。

输入格式

第一行输入一个正整数n，代表排列的大小。 第二行输入n个正整数ai，代表排列的元素。 1<=n<=200000 1<=ai<=n

输出格式

输出n个整数，第i个整数是f(i)的值。

输入数据1

3
1 2 3

输出数据1

0 1 2

提示

第一个元素取反，数组将变成[-1,2,3]，逆序对数量为 0。 第二个元素取反，数组将变成[1,-2,3]，逆序对数量为 1。 第三个元素取反，数组将变成[1,2,-3]，逆序对数量为 2。 请你使用树状数组进行解决，要求时间复杂度O(nlogn)