逆序对比赛

小童和小程日常相处并不是特别和睦，但他们两个都是爱好和平的人，一般出现有争执的事情，也不会吵架。 在编程的学习中，他们了解到一个“逆序对”的东西，它是这样定义的：给定一段正整数序列，逆序对就是有两个数字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。

时间限制: 1000ms

内存限制: 256MB