问题说明

Gold King家的羊的饲养方式很高大上，每只羊有单独的一间羊舍（编号:1-n），每天又会按时单独放一只羊到牧场上定时进食，按理说每只羊的生长量应该相同，但是却有一些羊的体重比其他羊重，很不寻常。Gold King想找出这样的一组羊：第i号羊的体重a比第j号羊的体重b大的，但i小于j的。请你帮Gold King找一下有多少组这样的羊。

输入格式

第一行输入n，表示有n只羊。
接下来输入n个数，表示n只羊的体重。

输出格式

输出满足要求的羊组个数。

4
6
8
5
3

5

提示

 n<=100000
 

来源/分类

算法培训-05-分治（归并、快排等）