#3. 逆序对

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: syzoj

题目描述

给出一个数列 a , 求其逆序对数量。

输入格式

输入共 2 行。

第一行,整数 n , 代表数组 a 的长度。

第二行, n 个整数, 代表 a 中的元素。

输出格式

输出仅一个整数, 数组中的逆序对数量。

样例

输入样例 1

5
2 4 3 1 5

输出样例 1

4

输入样例 2

10
5 5 4 4 3 3 2 2 1 1

输出样例 2

40

数据范围与提示

1 \leq n \leq 32768 , 1 \leq a_i \leq 32768