2586: 逆序对比赛

题目描述

小童和小程日常相处并不是特别和睦，但他们两个都是爱好和平的人，一般出现有争执的事情，也不会吵架。
在编程的学习中，他们了解到一个“逆序对”的东西，它是这样定义的：给定一段正整数序列，逆序对就是有两个数字a_i和a_j，满足a_i>a_j ，同时i<j。其中i和j是两个数字在序列中的位置编号。
掌握这个概念后，面临有争执的问题，他们决定通过比赛谁先算出一段正整数序列中逆序对的数目，这个问题就听谁的。注意序列中可能存在重复的数字。

输入描述

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

输出描述

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

5
5 2 6 3 1

7

数据范围与提示

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