2978 逆序对比赛

题目描述

小童和小程日常相处并不是特别和睦，但他们两个都是爱好和平的人，一般出现有争执的事情，也不会吵架。

在编程的学习中，他们了解到一个“逆序对”的东西，它是这样定义的：给定一段正整数序列，逆序对就是有两个数字 $a_i$ 和 $a_j$，满足 $a_i > a_j$，同时 $i < j$。其中 $i$ 和 $j$ 是两个数字在序列中的位置编号。

掌握这个概念后，面临有争执的问题，他们决定通过比赛谁先算出一段正整数序列中逆序对的数目，这个问题就听谁的。注意序列中可能存在重复的数字。

输入格式

第一行一个整数 $n$，表示序列中有 $n$ 个正整数。

第二行包括 $n$ 个正整数，表示给定的序列，每个数字不超过 10 亿。

输出格式

一个整数，表示序列中逆序对个数目。

样例输入 #1

5
5 2 6 3 1

样例输出 #1

7

数据范围

$1000 < n \le 100000$

序列中每个数字不超过 $10^9$。

时限 1000ms，内存限制 256MB。

样例中给定序列 5 2 6 3 1，存在 5 组逆序对：5 与 2，5 与 3，5 与 1，2 与 1，6 与 3，6 与 1，3 与 1。

知识点与难度

本题涉及的知识点从属于 GESP四级（归并排序、逆序对统计），难度等级：Mid。

测试点分布