2089: 宝典2第五章求逆序对数

【题目描述】求逆序对数（reverse. cpp/c/pas）

“装满了鹅卵石的瓶子是满的吗？”墨老师曾经这样问过他的学生。“不是，因为还可以放入小石子、再放入细砂、最后再倒入水。”学生们回答。“那么从中可以得到什么启示呢？”墨老师又问，“启示我们时间总是可以挤出来的！”一个聪明的学生抢答。“你说得对！”墨老师微笑道，“但我还要告诉你们另一个重要经验，那就是：如果你不先将大的鹅卵石放进瓶子里去，你也许以后永远没机会再把它们放进去了。”

但这世上的很多人，做事却经常分不清事情的轻重缓急。我们可爱的典狱长大人就犯了这个错误，当他看到身高参差不齐的狱警们排成一列时，眉毛拧成了一个结，他最想知道的就是，到底有多少个狱警逆序排队了。这可以抽象为求逆序对的个数问题：即对于一个包含n个非负整数的数组A[1，…，n]，如果有i < j，且A[ i ]>A[ j ]，则称(A[ i] ，A[ j] )为数组A中的一个逆序对。

例如，数组（3，1，4，5，2）的逆序对有(3，1)，(3，2)，(4，2)，(5，2)共4个。

【输入文件】

输入文件reverse.in包括两行，第一行是一个整数n(1≤n≤1000)，表示狱警人数。第二行包含n个整数，用空格分隔，即每个狱警的身高，狱警身高均在int范围内。

【输出文件】

输出文件reverse.out包括一行，这一行只包含一个整数，即逆序对的个数。

【样例输入】

５

３　１　４　５　２

【样例输出】

４