Migrated from Lutece 2722 啥b二次元

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Yo 决定和他女朋友分手，全身心投入二次元。 Yo 决定入坑某个二次元抽卡游戏。 Yo 将他和女朋友的花销全部充到游戏里面，抽到了 $n$ 张卡，每张卡有个战力值，这 $n$ 张卡的战力为 $[1,n]$ 的排列。 但是由于这个游戏非常有病，仓库里所有卡是按照某种顺序排列，排在第 $i$ 个的卡牌战力值为 $v_i$。而有强迫症的 Yo 会因为战力顺序错乱不爽。 具体的，每存在两张卡牌在仓库第 $i$ 个和第 $j$ 个位置而且满足 $i<j,v_i>v_j$，Yo 就会产生 $1$ 的不爽度。即 Yo 的不爽度是已有卡牌序列的逆序对数。 Yo 会给出他这 $n$ 次每次抽出的卡的战力值，他想知道每次抽卡后自己的不爽值。 由于他还要玩二次元游戏，所以他将这个问题交给你了。

Input

第一行输入一个整数 $n$。 第二行输入 $n$ 个空格隔开的整数表示仓库卡牌序列的战力值 接下来 $n$ 行每行一个整数表示 Yo 依次抽到的卡的战力值

Output

输出 $n$ 行每行表示抽到一张卡后 Yo 的不爽值

Samples

10
6 10 7 5 8 9 2 1 4 3 
3
4
7
9
10
5
8
1
6
2

0
1
3
5
9
13
16
21
25
32

Constraints

$1\le n\le 10^5$ 保证输入数列为 $[1,n]$ 的排列

Note

样例解释： 仓库中卡牌序列分别如下：

• 3
• 4 3
• 7 4 3
• 7 9 4 3
• 10 7 9 4 3
• 10 7 5 9 4 3
• 10 7 5 8 9 4 3
• 10 7 5 8 9 1 4 3
• 6 10 7 5 8 9 1 4 3
• 6 10 7 5 8 9 2 1 4 3

Resources

2022 UESTC ICPC Training for Data Structures