清点逆流

G-30矿区的第一颗监控水晶嵌在入口处的岩壁上。它记录的不是画面，是"秩序度"——每个经过的物体都会在水晶里留下一个数字，代表它对这个区域秩序的影响。数字越小，代表越混乱；数字越大，代表越有序。

"Zero用前后颠倒的数字对来衡量混乱。"Echo飘到水晶前，投影被水晶的蓝光染成了淡青色，"如果一个序列里，前面的数字比后面的数字大，就构成一对逆流。逆流越多，序列越混乱。"

CC看着水晶里流动的数字："这些数字……是三天来所有经过这里的物体的记录？"

"对。猎杀者、巡逻机、还有……"Echo停顿了一下，"还有Glados三年前留下的。"

"啥子？"CC猛地转头。

"水晶的记录不会被覆盖。Glados三年前来过这里，他的数字还在里面。"

你凑近水晶。数字流里，有大的，有小的，有杂乱无章的，也有整齐排列的。要找出逆流的数量——也就是统计有多少对数字，前面的比后面的大。

"一个个数太慢了。"你说，"换个办法——倒着翻账本。从最后一名开始往前翻，每遇到一个数字，就查查比它小的数字已经出现过多少个。"

"咋个查？"CC皱眉。

"建一个分层名册。"你说，"像一棵倒过来的树，每个节点管一段编号范围。想知道某个范围内已经登记了多少个，不需要从头数，只需要往上爬几层。"

你开始写。先把所有数字编号——因为数字可能很大，但种类不多。然后从序列末尾往前扫描，用分层名册维护"已经出现过哪些数字"。每遇到一个数字，查询名册里比它小的数字有多少个——那就是以它为第二个元素的逆流数量。

屏幕上跳出了结果。逆流数量：2147。

"又是47。"CC说。

Echo没说话。但她的投影在水晶前停留了很久，像是一个人在墓碑前默哀。

题目描述

给定一个序列，求逆序对数量。

输入格式

$n$。然后 $n$ 个整数。

输出格式

逆序对数量。

输入样例

5
1
2
1
0

输出样例

2
4
5
3
1

提示

• 离散化后，从后往前扫描。
• 用树状数组维护已出现数字的个数，查询比当前数小的已出现个数。
• 时间复杂度 $O(n \log n)$。

水晶的光芒暗了一瞬，像是某种古老的机关被触动。Echo的投影从水晶前退开，转向矿道深处。

"下一颗水晶在中段。"她说，"那里记录的是矿道的能量密度——每一段的GCD。"

"GCD？"CC问。

"最大公约数。"Echo说，"所有段的能量值共享的一个基准。"

"那如果改了一段，岂不是要全部重算？"

"所以要分段记账。"你说，"把矿道切成很多小段，每段的账目单独存。想知道整条矿道的情况，只需要把覆盖那几段的账目合并起来。"