题目描述

给你一个n个数的数列，求出它们的逆序数 所谓逆序，在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数 例如：数列 1 2 3 4 5 中，1的后面没有1个比自己小的，所以逆序对为0 ，2的后面也没有比自己小的，所以逆序对为0，以此类推，所以5个数的所有逆序对为0 而 数列       5 4  3 2 1 中， 5后面比5小的 有 4,3,2,1，所以5和后面的4个数都构成逆序对（即：(5,4）(5,3）(5,2) (5,1)总计有4个逆序对 同理 4 和 3 2 1也构成逆序对，所以 4构成了3个逆序对，一次类推， 5 4 3 2 1构成的逆序对个数是 4  +  3 + 2 + 1=10个

输入格式

第一行输入一个数n，代表此数列一共有多少个数 第二行输入n个数的数列 题目保证n和数列中的数都是正整数，且不会超过100 有多个输入，请使用循环读入

输出格式

输出每个数列的逆序数，每个输出占一行

5
1 2 3 4 5
5
5 4 3 2 1

0
10

提示

使用树状数组或者归并排序可以有效降低时间复杂度