B. 交易逆序对的总数

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

题目描述

在股票交易中,如果前一天的股价高于后一天的股价,则可以认为存在一个「交易逆序对」。

请设计一个程序,输入一段时间内的股票交易记录 a,返回其中存在的「交易逆序对」总数。

输入格式

第一行,包含一个整数 n,表示交易记录的数量

第二行,包含 n 个整数,表示 n 个交易的股价

输出格式

「交易逆序对」总数

样例

输入:

5
9 7 5 4 6

输出:

8

解释:交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。

数据范围与提示

60%数据:0 <= n <= 10000

100%数据:0 <= n <= 100000