Inverse number:Reborn

时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 291 总提交人数: 440

题目描述

输入一个正整数n,随后给出一个长度为n的整数序列a1,a2,a3...an。求给定序列的逆序数。

概念回顾:

逆序对:数列a[1],a[2],a[3]…中的任意两个数a[i],aj,如果a[i]>a[j],那么我们就说这两个数构成了一个逆序对。

逆序数:一个数列中逆序对的总数。

输入

多组测试数据。对于每组测试数据,给出序列长度n,和一个长度为n的序列a1,a2,a3...an

(0<n<=10^6,保证ai在int范围内)

输出

对于每组数据,输出该序列的逆序数。

输入样例

7 
3 5 4 8 2 6 9

输出样例

6

Hint

1、用n^2的算法是不行不行滴╮(╯_╰)╭
2、分治法