题目描述
Tom猫和Jerry鼠成为了好朋友。他们最近在玩一个数逆序对的游戏。
逆序对这东西是这样定义的:对于给定的一段正整数序列,逆序对就是序列中a[i]>a[j]且i<j的有序对。也就是说在一个序列里面,序列前面的某个数大于后面的某个数,这种两个数组合在一起就是一个逆序对。知道这概念后,他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。
输入
第一行,一个数n,表示序列中有n个数。 第二行n个数,表示给定的序列。输出
给定序列中逆序对的数目数据范围
2 <= n<= 10^5输入样例
42 8 5 3